[백준 14860] GCD 곱 [C]

백준 - 14860

---

풀이

위의 예제는 다음과 같은 규칙이 있다.

• gcd(1, 소수) = 1 이므로 계산할 필요가 없으며, gcd(소수, 소수) = 소수 이다. 
• gcd(N, M) = K일 때, gcd(N + K*i, M + K*i)는 모두 K이다. (단, i = 2~N or M)
• 위의 조건에서 얻은 K는 K의 제곱수가 존재할 경우 변경된다.

N과 M크기를 이용해 K의 개수를 구할 수 있다.

 

두번째 조건에서 얻은 K들의 곱들과 세번째 조건에서 얻은 수의 중복을 피해야 한다.

다음과 같이 p+K*i (단, i = 0 ~ (p+K*i <= N))에 대해 visited에 기록해준다.

for (LL i = 2; i <= N; i++)
    if (!visited[i]){
        for (LL p = i*i; p <= N; p += i)
            visited[p]++;

 

 

i의 제곱수들에 대해 다음과 같이 x^n을 temp에 담고 result와 곱해주었다.

for (LL j = i; j <= N; j *= i){
    LL x = i, n = (N/j)*(M/j), temp = 1;
    "
    x^n을 구해서 temp에 담아준다.
    "
    result = result * temp %MOD;
}

 

 

만약 GCD(8, 8)을 구하고자 하면 다음과 같을 것이다.

i의 제곱수	x^n	temp
2	2^16	65,536
4	2^4	16
8	2^1	2
3	3^4	81
5	5^1	5
7	7^1	7
result	945,425,885

---

소스코드

#include <stdio.h>
#include <stdbool.h>
#define MOD 1000000007
#define LL long long
char visited[15000001];
int main(){
    int N, M;
    LL result = 1;
    scanf("%d %d", &N, &M);
    for (LL i = 2; i <= N; i++)
        if (!visited[i]){
            for (LL p = i*i; p <= N; p += i)
                visited[p]++;
				
            for (LL j = i; j <= N; j *= i){
                LL x = i, n = (N/j)*(M/j), temp = 1;
                while (n > 0){
                if (n & 1) temp = temp*x %MOD;
                    x = x*x %MOD;
                    n >>= 1;
                }
                result = result * temp %MOD;
            }
        }
    printf("%lld", result);
}

---

출처

14860번: GCD 곱