백준[baekjoon] 6064

www.acmicpc.net/problem/6064

6064번: 카잉 달력

 

[잡담]

정수론 공부의 필요성을 느껴 유투브 보면서 기초부터 공부하고있다.

모듈러 기초연산부터 페르마 소정리, 중국인의 나머지 정리, 뤼카의 정리등 처음볼때는 전혀 이해가 안갔지만

이항계수 정리등 블로그로 부족한 개념을 채우다 보니 어느정도 이해하게 되었다.

지금이라도 수학공부를 꾸준히 해놔야겠다.

[코드]

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

tuple<int,int,int> extended_euclidean(int a, int b)
{
    if(b == 0) return make_tuple(a,1,0);

    int g, x, y;
    tie(g, x, y) = extended_euclidean(b, a%b);
    return make_tuple(g, y, x-(a/b)*y);
}

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);

    int TC;
    cin >> TC;
    while(TC--){
        int M, N, x, y;

        cin >> M >> N >> x >> y;

        int g, x0, y0;

        tie(g, x0, y0) = extended_euclidean(M, N);
        if((x-y)%g != 0){
            cout << -1 << '\n';
            continue;
        }

        LL lcm = M*N/g;
        LL ans = 1LL*(y-x)*x0/g*M + x;
        ans %= lcm;
        while(ans<0){
            ans += lcm;
        }

        cout << ans << '\n';
    }

    return 0;
}