[백준] GCD 곱

문제 : https://www.acmicpc.net/problem/14860

 

문제요약 : GCD(1, 1) × GCD(1, 2) × ... × GCD(1, M) × GCD(2, 1) × GCD(2, 2) × ... × GCD(2, M) × ... × GCD(N, 1) × GCD(N, 2) × ... × GCD(N, M)을 구해라

 

조건 :

1. 1 ≤ N, M ≤ 15,000,000

 

해설 :

i) Naive Solution

각각의 i(1 ≤ i ≤ N), j(1 ≤ j ≤ M)에 대해 GCD(i, j)를 구해 곱하면서 O(NM)으로 구할 수 있겠죠?

-> 15000000^2이므로 너무 느립니다

 

ii) 조금더 빠르게

N=8, M=8이라 합시다. GCD(i,j)들 중에 2의 인수가 얼마 있는지 알아봅시다.

	1	2	3	4	5	6	7	8
1
2		2		2		2		2
3
4		2		4		2		4
5
6		2		2		2		2
7
8		2		4		2		8

이제 알 것 같나요?

2의 인수는 sum([n/j]*[m/j] for j = 2^0, 2^1, 2^2, ...)개 있습니다.

min(n,m)까지의 소수들을 구하고 각각의 소수 p에 대해 

z = sum([n/j]*[m/j] for j = p^0, p^1, p^2, ...)

를 구하고 해답에 p^z을 곱하면 됩니다. (pow연산은 O(log z)죠?)

 

소스코드 :

#include <stdio.h>
typedef long long ll;
const ll M=1e9+7;
bool v[20000000];
 
ll lpow(ll m, ll t){
    if(t==1) return m;
    if(t==0) return 1;
    ll x=lpow(m,t/2)%M; x=(x*x)%M;
    return (x*((t%2)?m:1))%M;
}
 
int main(){
    ll n, m, i, j, p, t;
    scanf("%lld%lld",&n,&m);
    for(t=0, j=2; j<=n; j*=2) t+=((n/j)*(m/j));
    p=lpow(2,t)%M;
    for(j=4; j<=n; j+=2) v[j]=true;
    
    for(i=3; i<=n; i+=2){
        if(!v[i]){
            for(t=0, j=i; j<=n; j*=i) t+=((n/j)*(m/j));
            p=(p*lpow(i,t))%M;
            for(j=i*i; j<=n; j+=i*2) v[j]=true;
        }
    }
    printf("%lld",p%M);
}