7466

static int N, K;

static int solution(void)
{
	int gcd = 1;

	scanf("%d %d", &N, &K);

	for (int div = 2; div <= K; div++) //2부터 K 까지로만 나눌 수 있음,
	{
		int val = 1, cur = div * val;

		while (K % div == 0) //div가 K의 소인수라면,
		{
			K /= div;

			if (cur <= N && !(cur % div))
			{ 
				gcd *= div; //gcd에 추가
				cur /= div;
			}
			
			if (cur % div)
				cur = div * (++val);
		}
	}

	return gcd;
}

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

실제로 N!을 구하고, 유클리드 호제법을 이용하여 최대 공약수를 구할 순 있지만,

최대 10억까지 입력으로 들어오기 때문에 10억! 을 저장 할 수도 없을 것이고, 10억! 을 구하는데 시간을 다 쓸 수도 있다. 그래서 아래와 같은 방법을 코드로 구현하였다.

 

먼저 10 과 2*2*2*2*2*3*5*5*7 을 예로 들자면,

 

           10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 

-------------------------------------------------------

       7 * 5 * 5 * 3 * 2 * 2 * 2 * 2 * 2 

 

분모의 첫번째 2가 분자의 2를 나누고, 분모의 두번째 2와 세번째 2가 분자의 4를 나누고, 분모의 네번째 2가 분자의 6을 나누고, 분모의 마지막 2가 분모의 8을 나누는 것이다. 이렇게 생긴 4는 더 이상 나누어지지 않는다. 

이는 분모는 소수로만 구성되기 때문이다.  

 

마지막으로 7 과 2*2*2*2*2*3*5*5*7 을 예로 들자면,

 

                7 * (6) * 5 * (4) * 3 * (2) 

--------------------------------------------------------

       7 * 5 * 5 * 3 * 2 * (2) * (2 * 2) * (2) 

 

분모의 마지막 2는 8이 없으므로 gcd에 포함되지 않게 된다.

이런 식으로 최대공약수를 구해나가는 것이다.