10진법 정수를 등비수열 합으로 바라보기(Fermat number?)

1. 문제

 

22445번: Fast Division (acmicpc.net)

22445번: Fast Division

 

일본어로 되어있는데 번역하면

 

$2^{2^{2^{2..}}}$로 총 2가 n개 있을때, 이 값보다 크거나 같은 최소의 소수를 p(n)이라고 정의하자.

 

여기서 p(0) = 2라고 한다.

 

p(n)-1자리의 10진법 정수 1111....을 p(n)으로 나눈 나머지를 구한다면?

 

2. 풀이

 

p(n)을 한번 구해보면..

 

p(0) = 2

 

p(1) = 2보다 큰 최소의 소수 3

 

p(2) = 4보다 큰 최소의 소수 5

 

p(3) = 16보다 큰 최소의 소수 17

 

p(4) = 256보다 큰 최소의 소수 257

 

p(5) = 65536보다 큰 최소의 소수 65537

 

로 $2^{2^{2...}}$를 계산하고 나서 거기에 1을 더하면 될 것 같은데..

 

p(6) = 4294967296보다 큰 최소의 소수... 4294967297은 소수가 아니라고 한다

 

https://en.wikipedia.org/wiki/Fermat_number

Fermat number - Wikipedia

 

글을 읽어보면 p(6)부터는 알려져있지 않은듯...

 

그래서 조금 다르게 접근해보면

 

구하고자 하는건 111111111111111..... mod p(n)인데... 이 11111111111111111.........은 다음과 같이 나타낼 수 있다

 

$$1111111... = 10^{p(n) - 2} + 10^{p(n) - 3} + ... + 10 + 1 = \sum_{k = 0}^{p(n) - 2} 10^{k}$$

 

즉, 111111....은 초항이 1이고 공비가 10이며 항수가 p(n)-1인 등비수열의 합으로 나타낼 수 있다

 

그러므로, $$\frac{10^{p(n)-1} - 1}{10-1} mod p(n)$$을 구하는 문제가 된다.

 

그런데, p(n)이 소수이므로, 페르마의 소정리에 의하면 $$10^{p(n) - 1} mod p(n) ≡ 1$$

 

그리고 필요한건 $9^{-1} mod p(n)$인데, 이 값이 뭐가 됐든지 간에 $10^{p(n) - 1} mod p(n) ≡ 1$이므로,

 

$$\frac{10^{p(n) - 1} -1}{10-1} mod p(n) ≡ 0$$

 

한가지 문제는 페르마의 소정리가 성립할려면, p(n)과 10이 서로소여야한다.

 

10 = 2*5이므로, p(n)이 2거나 5이면 서로소가 아니라서 성립하지 않는다.

 

p(0) = 2이고 p(2) = 5이므로 이 경우에는 직접 구해야한다

 

그리고 또 하나의 문제는, $9^{-1} mod p(n)$이 존재해야하는데, 9와 p(n)이 서로소여야한다.

 

하지만 p(1) = 3이면 서로소가 아니라 존재하지 않는다. 그래서 이 경우도 직접 구해야한다.

 

즉 n = 0, n = 1, n= 2인 경우는 직접 구하고, $n \geq 3$인 경우는 무조건 0이다

 

사실 직접 구할필요도 없이 예제로 n = 0,1,2인 경우 값이 제시되어있다

 

 

n = int(input())

if n == 0 or n == 2:
    
    print(1)

elif n == 1:
    
    print(2)

else:
    
    print(0)