[BOJ] 7806: GCD!

1. PROBLEM

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

문제

두 수의 최대공약수는 두 수를 나머지 없이 나눌 수 있는 가장 큰 자연수로 정의한다. 예를 들어, 8과 12의 최대공약수는 GCD(8,12)로 나타내고, 그 값은 4이다. 4는 8과 12를 나눌 수 있는 가장 큰 정수이기 때문이다. (8과 12의 공약수는 1, 2, 4가 있다)

자연수의 팩토리얼은 그 수보다 작거나 같은 모든 양의 정수의 곱이다. 예를 들어, 5의 팩토리얼은 5!로 나타내고 1*2*3*4*5 = 120이다. (0!은 1로 정한다)

두 수 n과 k가 주어졌을 때, n!과 k의 최대공약수를 구하는 프로그램을 작성하시오. 예를 들어, n = 3, k = 10이라면, GCD(n!,k) = GCD(3!,10) = GCD(1*2*3,10) = GCD(6,10) = 2가 된다.

입력

각 줄에 n과 k가 하나씩 주어진다. (0 ≤ n ≤ 1,000,000,000, 1 ≤ k ≤ 1,000,000,000)

출력

입력의 각 줄에 대해서, n!과 k의 최대공약수를 출력한다.

2. SOLUTION

#1. 시간 초과(TLE) 발생

[참고] 시간 초과(TLE) 해결 방법

import sys
import math

input = sys.stdin.readline
n, k = map(int, input().split())

result = math.gcd(math.factorial(n), k)
print(result)

팩토리얼 연산 자체가 큰데, 거기에다가 gcd 연산까지 하니까 너무 무거워졌나보다.

방법을 찾아보니 소인수분해 + Legendre(르장드르) 공식을 사용하면 해결된다는데... 일단 이 공식 자체가 머리 아픔....

이건 다음에 조금 더... 성장하고 다시 풀기로 하자..🙂‍↔️

소인수분해 + Legendre(르장드르) 공식

예