[백준] 7806번 GCD!

문제

https://www.acmicpc.net/problem/7806

 

풀이

 

처음에는 n!을 기준으로 gcd(n,k) , gcd(n-1,k / gcd(n,k)) 이런 식으로 최대공약수를 구해나가려고 했습니다. 이런 식으로 구현하게 되면 시간초과가 발생합니다.

 

이 문제의 경우에는 K를 기준으로 소인수분해하고 해당 소수가 n!에 몇 개 존재하는 지 찾아내서 지수가 작은 수를 통해 최대공약수를 구하는 방식으로 구현해야 합니다.

 

n! 을 소인수분해 할 때 일반적으로 사용되는 것처럼 소수로 계속 나누게 되면 엄청난 시간이 걸립니다.

n! 을 소인수분해 할 때는 n / 소수^1 + n / 소수^2 + n / 소수^3 ... 하시면 n! 을 소인수분해 했을 때 소수 갯수를 구할 수 있습니다.

 

소스코드

#include <iostream>
#include <cmath>

using namespace std;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, k;

    while(true){

        cin >> n >> k;

        if(cin.eof()) break;
        
        long long int ans = 1;

        // 소인수분해해서 최대공약수 찾기
        for(int i = 2; i*i <= k;i++){
            
            int primeCntOfK = 0;
            while(k % i == 0){
                k /= i;
                primeCntOfK++;
            }

            int primeCntOfN = 0;
            if(primeCntOfK > 0){

                // n! 의 소인수분해
                for(int j = i; j <= n; j *= i)
                    primeCntOfN += n / j;
            }

            ans *= pow(i,min(primeCntOfN,primeCntOfK));

            if(k < i) break;
        }
        // n! 을 소인수분해 했을 때 n이 넘는 소수는 존재하지 않는다.
        // 남은 수는 무조건 소수이므로 곱해준다.
        if(k > 1 && k < n) 
            ans*= k;

        cout << ans << "\n";
    }

    return 0;
}