디오판토스 분수방정식의 정수 해법 배우기(+팩토리얼 인수분해, 제곱수의 약수의 개수)

1. 문제1

 

7516번: 알렉산드리아의 디오판토스 (acmicpc.net)

7516번: 알렉산드리아의 디오판토스

 

2. 풀이

 

주어진 방정식 $\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$을 정리하면,

 

$$\frac{y+x}{xy} = \frac{1}{n}$$이다.

 

그래서 $$n(y+x) = xy$$를 얻는다.

 

솔직히 여기서 넘어가기 어려운데, (억지라는 생각이 들 정도..)

 

$n^{2} = pq$라 하자. p,q는 정수이다. 즉, p,q는 $n^{2}$의 약수이다.

 

그리고 $$x = p + n$$, $$y = q + n$$이라고 하자.

 

그러면, $n(y+x) = xy$는 다음과 같이 변한다.

 

$$n(p+q+2n) = n(p+q) + 2n^{2} = pq + n(p+q) + n^{2}$$

 

그런데, $pq = n^{2}$이라 가정했으므로, 우변이 $n(p+q) + 2n^{2}$으로 좌변과 동일해진다.

 

그러므로, $n^{2}$의 약수 p,q를 구하면, $x = p + n$과 $y = q + n$으로 반드시 해를 구할 수 있다.

 

즉, 문제는 $n^{2}$의 약수의 개수를 구하는 문제로 바뀐다.

 

근데 n의 제한이 $10^{9}$이고 쿼리 문제이면서 시간제한이 1초라서.. $O(N)$보다 훨씬 빠르게 $n^{2}$의 약수 개수를 구해야함

 

약수의 개수는 소인수분해를 해서, 소인수 지수 + 1의 곱으로 구할 수 있는데..

 

https://deepdata.tistory.com/588

약수의 합과 약수의 개수 공식 익히기

 

소인수분해는 $O(\sqrt{n})$이라서, $O(\sqrt{n^{2}}) = O(n)$으로 할 수 있겠지만.. $10^{9}$는 1초안에 돌 수 없어

 

하지만 n을 소인수분해해서 $n = p_{1}^{k_{1}}p_{2}^{k_{2}}...$으로 구한다면...

 

$$n^{2} = p_{1}^{2k_{1}}p_{2}^{2k_{2}}...$$으로 바로 구할 수 있으니까..

 

$$(2k_{1}+1)(2k_{2}+1)...$$으로 구할 수 있겠지

 

$10^{4}$정도는 0....몇초만에 아주 빠르게 구할 수 있으니 쿼리 문제더라도 문제 없을듯

 

또 하나 고려해야할 문제는 $x \leq y$라는 조건이다

 

단순히 약수의 개수만 구해버리면, $x > y$를 만족하는 (x,y)도 구해지니.. 조금 생각해야한다

 

예를 들어 n = 4라고 한다면.. $n^{2} = 16$의 약수는

 

1,2,4,8,16으로 (p = 1, q = 16), (p = 2, q = 8), (p = 4, q= 4)로 3개이다.

 

n = 8이라고 한다면.. 

 

1,2,4,8,16,32,64로 (p = 1, q = 64), (p = 2, q = 32), (p = 4, q = 16), (p = 8, q = 8)로 4개이다.

 

제곱수 $n^{2}$의 약수는 홀수개로 2k+1개인데... 1개를 제외한 2k개는 서로 2개씩 짝지어서 k개이고 

 

제외된 1개는 p = n, q = n인 경우로 이거 1개를 더해서 k+1개가 정답

 

즉, 소인수분해하면서, 소수의 지수를 count로 구해주는데, 더이상 n이 안나누어지면, count를 2배해주고

 

거기에 1을 더한 값을 answer에 누적시켜준다 

 

그 answer를 2로 나눠주고 1을 더해주면 그것이 정답

 

#1/x + 1/y = 1/n의 정수해 (x,y)의 개수 (x<=y)
#n^2 = pq, x = p + n, y = q + n이 일반해

from sys import stdin

T = int(stdin.readline())

for i in range(1,T+1):
    
    n = int(stdin.readline())

    p = 2

    answer = 1
    
    #n에 대한 소인수분해로 n^2의 약수의 개수를 구해준다
    while p*p <= n:
        
        count = 0

        while n % p == 0:
            
            count += 1
            n//= p
        
        #n에서 소수 p에 대한 지수가 count
        #n^2에서 소수 p에 대한 지수는 2count
        #2count+1을 누적곱해준다
        count *= 2
        answer *= (count+1)
        p += 1
    
    if n > 1:
        
        answer *= 3
    
    #제곱수 n^2의 약수의 개수는 홀수개 = 2k+1
    #x <= y인 (x,y)를 구해야하므로, 2k개끼리는 서로 짝지어주어서 k개
    #나머지 1개인 p = n, q = n을 더해주면 k+1개가 정답
    answer //= 2
    answer += 1
        
    print(f'Scenario #{i}:')
    print(answer)
    print()

 

3. 문제2

 

13723번: 팩토리얼 분수 방정식 (acmicpc.net)

13723번: 팩토리얼 분수 방정식

 

4. 풀이

 

위에서 해결한 문제의 특수형태

 

n이 n!로 바뀐 것 뿐이다.

 

즉, $(n!)^{2}$의 약수의 개수가 정답이 된다

 

팩토리얼의 소인수분해를 통해, 팩토리얼 제곱의 약수의 개수를 구해줘야한다.

 

https://deepdata.tistory.com/908

팩토리얼을 계산하지 않고도 소인수분해하는 기본기

 

n이하의 모든 소수를 에라토스테네스의 체를 이용해 찾고, 해당 소수 리스트를 순회해서,

 

n!이 가지는 p의 지수를 찾아준다

 

k = p라고 저장해놓고, n//k가 0이 될때까지 k에 p를 반복적으로 곱하면서, 반복적으로 n//k를 누적합해준다.

 

그러면 그 지수의 2배를 해서, 1을 더해준 값을 누적곱해주면 그것이 정답

 

x,y의 크기에 대한 조건이 없으므로, 정확히 $(n!)^{2}$의 약수의 개수가 정답이다

 

def get_prime(n):
    
    result = [1]*(n+1)

    for i in range(2,int((n**(1/2))+1)):
        
        if result[i] == 1:
            
            for j in range(i*i,n+1,i):
                
                result[j] = 0
    
    return [i for i in range(2,n+1) if result[i] == 1]

n = int(input())

answer = 1

primes = get_prime(n)

for p in primes:
    
    k = p
    count = 0

    while n//k != 0:
        
        count += n//k

        k *= p
    
    count *= 2
    answer *= (count+1)

print(answer)