GCD, LCM

최대공약수, 최소공배수

최대공약수 (GCD) - 유클리드 호제법

int gcd(int n, int m)
{
    while(n) {
        int t = m%n;
        m = n;
        n = t;
    }
    return m;
}

최소공배수 (LCM)

int lcm(int n, int m)
{
    int g = gcd(n, m);
    return g*(n/g)*(m/g);
}

페르마의 소정리에 이용되는 원리

먼저 a와 p가 서로소라고 하자. 이때 1a,2a,⋯,(p−1)a는 mod p 에 대해 서로 합동이 아니다. 또한 이중에서 p의 배수인 것은 없으므로, 이 ka들을 p로 나눈 나머지들의 집합은 {1,2,⋯,p−1}와 같다.

https://codeforces.com/contest/1260/problem/C