13723 팩토리얼 분수 방정식

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

 

풀이

양의 정수 X,Y이므로 부호에 따른 조건과 정수꼴로 나타내지는 조건(특정한 수로 나누는 것과 같은 조건)이 필요함을 추측할 수 있다

1/N! = (X + Y)/XY

양변에 N!XY를 곱해주자 XY = N!(X+Y)

어떤 특정한 두 수를 곱하는 것으로 생각해볼 수도 있고 X와 Y의 관계로 나타내 볼 수 있다

후자가 더 쉬워보이므로 후자를 해본다

N!X + N!Y - XY = 0

N!X + Y(N!-X) = 0

N!X = Y(X-N!)

N!X/(X-N!) = Y

양의 정수만을 다루므로 해당 과정이 성립한다.

X > N!이므로 X를 N!+k으로 생각할 수 있다. (k는 양의 정수(

식을 정리해보자.

X = N! + k 라면 Y = N!(N!+k)/k 이다.

X는 어차피 양의정수고, Y를 정수로 만드는 k의 개수만 찾으면 된다.

Y = N!(N!+k)/k = (N!^2)/k + kN!/k = (N!^2)/k + N! = 정수

따라서 N!^2의 약수 개수를 찾으면 된다. 

약수의 개수는 소인수 분해를 통해 찾을 수 있다.

T = f1^p1 + f2^p2 + ... + fi^pi일때 약수의 개수는 (p1+1)(p2+1)...(pi+1)이다.

왜냐하면 0개를 선택하는 것 부터(1) 모든 소인수를 선택하는 것 까지(T) 개수를 세어야하기 때문이다.

N!^2을 소인수 분해하기 어렵다. 따라서 N!을 소인수 분해하자.

N!은 N(N-1)(N-2)...1 이고 a^x * a^y = a^(x+y) 이다.

따라서 1부터 N까지 각각의 수를 소인수 분해하고 그 결과들을 합쳐주면 된다.

소인수_테이블 = {}
for int i를 1부터 N:
	for int j를 1부터 sqrt(i):
    		while i % j == 0:
        		소인수_테이블[j] += 1
            		i = i / j

N!을 소인수 분해했다면 N!^2은?

(a^x)^2 = a^2x 이므로 테이블의 value를 2씩 곱해준다.

그리고 약수의 개수를 구하면 된다.