7806 GCD!

n! 과 k 의 최대공약수를 구하는 문제이다.

n!은 매우 큰 숫자기 때문에 long long 형의 범위도 가볍게 넘어버린다.
그러나 k가 int 형 범위이기 때문에 결과는 최대 공약수가 나와서 big integer를 구현할 필요는 없다.

이 문제를 풀기 위해선 k를 소인수 분해할 필요가 있다.
k를 소인수 분해 하는것은 소수판별 할 때 처럼, 2부터 root(k)까지만 검사하면 된다.
푸는 방법을 의사 코드로 나타내 보았다.

s = 1;
for(i = 1; i <= sqrt(k); i++)
{
  p = 0;
  while(k % i == 0)
  {
    b /= i;
    p++;
  }
  if (p)
  {  
    // n!에서 인수 i가 몇개 존재하는가
    k = primeFactorCountOfFactotial(n,i); 
    s *= pow(i,k);
  }
}
print s;

primeFactorCountOfFactorial(n,i)
{
  result = 0;
  for(j = i; j <= n; j *= i)
  {
    result += (int)(n / j);
  }
  return result;
}

소스