2014년 7월 23일 수요일

7806 - GCD!

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

n!과 k를 각각 소인수분해해서 각 겹치는 인수들 중에 지수가 더 작은 것끼리 곱하면 그것이  n!과 k의 공약수이다.

예를 들어, (n=4)!, k=18 이라면 4! 을 소인수분해하면 23x3 이고 18 은 2x32 이다. 겹치는 인수는 2, 3 이고 지수가 더 작은 것끼리 곱하면  21x31 = 6 이다.

매개변수 p를 두고 p=2 부터 $p^2 \le k$ 까지 늘려가면서 아래 작업을 수행한다.

n에서 pa 를 알아내고, k에서 pb 를 알아내서 result 에 pmin(a,b)를 중첩하여 곱셈했다.
댓글 쓰기

게시글 목록