[7806번] GCD!

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 소인수 분해

n과 m이 있을 때 n!과 m의 gcd를 찾아야하는데 이때 m을 소인수 분해를 할 때 

root(m)까지만 찾아주면 된다는 소인수 분해 특징을  생각하고 풀면 해결 할 수 있다.

코드를 보면 다음과 같다.

i가 2부터 root(m)까지 반복되는데 이때 i가 m에 나누어떨어지면 powM을 +1 해준다.

두번째로 powM이 1이상이면 n에는 powN이 몇개가 되는지 체크해준다.

그렇게 gcd를 만들어나가고 마지막으로 m이 1보다 큰데 m <= n이면 마지막 그 수를 곱해줌으로써 최종 gcd를 만든다.

예를들어 28과 22를 보면 다음과 같다.

28!과 22의 gcd는 2가 하나 나오게 되고 28!/2와 11이 있는데 

이때 m > 1이면서 m <= n이니 11을 곱한 최종 22가 gcd가 된다는 것이다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n, m;
 
    while(~scanf("%d %d", &n, &m))
    {
        long long tmp = m;
        long long ans = 1;
        for (int i = 2; i*i <= tmp; i++)
        {
            int powM = 0;
            // m에 i가 몇개 들어있는지 확인
            while(m % i == 0)
            {
                m /= i;
                powM += 1;
            }
 
            // i가 1개이상 들어있다면
            if (powM)
            {
                int powN = 0;
                // n에는 i가 몇개 있는지 확인
                for (int j = i; j <= n; j *= i)
                    powN += n / j;
 
                // powN와 powM는 서로 m과 n의 지수승을 의미(m^powN , n^powM)
                // 따라서 작은것을 따라감
                for (int j = 0; j < min(powN, powM); j++)
                    ans *= i;
            }
            
            if(m < i)
                break;
        }
 
        if (m > 1 && m <= n)
            ans *= m;
 
        printf("%lld\n", ans);
    }
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>