\({\phi }^2={\phi }+1\)
\(-1={\phi }-{\phi }^2\)
\(P_n=F_n{\phi }+F_{n-1}\)
\(=\large{\frac{{\phi }^{n+1}-\left(1-{\phi }\right)^n{\phi }}{\sqrt{5}}+\frac{{\phi }^{n-1}-\left(1-{\phi }\right)^{n-1}}{\sqrt{5}}}\)
\(=\large{\frac{{\phi }^{n+1}-\left(1-{\phi }\right)^{n-1}\left({\phi }-{\phi }^2\right)+{\phi }^{n-1}-\left(1-{\phi }\right)^{n-1}}{\sqrt{5}}}\)
\(=\large{\frac{{\phi }^{n+1}+\left(1-{\phi }\right)^{n-1}+{\phi }^{n-1}-\left(1-{\phi }\right)^{n-1}}{\sqrt{5}}}\)
\(=\large{\frac{{\phi }^{n+1}+{\phi }^{n-1}}{\sqrt{5}}=\frac{{\phi }^n}{\sqrt{5}}\left(\normalsize{\phi }+\large{\frac{1}{{\phi }}}\right)}\)
\(=\large{\frac{{\phi }^n}{\sqrt{5}}\left(\frac{\sqrt{5}+1}{2}+\frac{\sqrt{5}-1}{2}\right)}={\phi }^n\)
\(P_n=F_n{\phi }+F_{n-1}=\left(F_{n-1}+F_{n-2}\right){\phi }+F_{n-1}\)
\(=F_{n-1}\left({\phi }+1\right)+F_{n-2}{\phi }\)
\(=F_{n-1}{\phi }^2+F_{n-2}{\phi }\)
\(=F_{n-k}{\phi }^{k+1}+F_{n-k-1}{\phi }^k\)
\(\left(P_n\right)^k=\left({\phi }^n\right)^k={\phi }^{nk}=P_{nk}\)
\(=F_{nk}{\phi }+F_{nk-1}\)
\(=F_{nk-k+1}{\phi }^k+F_{nk-k}{\phi }^{k-1}\ \ \left[1\right]\)
\({\phi }^2-{\phi }=1\)
\(-{\phi }^3+2{\phi }^2=1\)
\(2{\phi }^4-3{\phi }^3=1\)
\(-3{\phi }^5+5{\phi }^4=1\)
\(...\)
\(\left(-1\right)^kF_{k-1}{\phi }^k+\left(-1\right)^{k-1}F_k{\phi }^{k-1}=1\)
\(\left(-1\right)^kF_{k-1}{\phi }^k+\left(-1\right)^{k-1}F_k{\phi }^{k-1}-1=0\ \left[2\right]\)
\([1]\) 식에 \([2]\) 식을 잘 곱해서 더해 \({\phi}^{k-1}\)을 제거하면 답이 나온다. \(\gcd(nk-k, k) = k\)니까 문제없이 나눗셈 가능. 근데 문제는\(\mod 1,000,000,007\)...
[이하는 https://www.acmicpc.net/board/view/70995의 내용을 보고 이해하여 새로 쓴 것.]
\(F_k\)가 \(1,000,000,007\)의 배수인 경우에는 따로 처리를 해 주어야 하는데, 이 때는 모듈러를 \({1,000,000,007}^2\)로 새로 잡아서 계산을 다시 하고 \(F_k\)와 \(F_{nk-k}\)를 구한 뒤에 둘 다 \(1,000,000,007\)로 나누어주면 다시 \(1,000,000,007\)를 모듈러로 두고 계산하는 데 문제가 없다.
정말 문제가 없을까? \(F_k\)가 \(1,000,000,007\)의 2승, 3승의 배수가 아니라는 보장이 어디에 있는가?
아래에 나와 있는 내용이다. 대충 적어도 \(p = 300\cdot 10^{15}\)까지는 그런 경우 없으니까 신경쓰지 말고 계산하면 되겠다...
Wall–Sun–Sun prime - Wikipedia
In number theory, a Wall–Sun–Sun prime or Fibonacci–Wieferich prime is a certain kind of prime number which is conjectured to exist, although none are known. Definition Let p {\displaystyle p} be a prime number. When each term in the sequence of Fibo
en.wikipedia.org
10908번: Phibonacci
두 번째 예제의 경우 \(\left(P_3\right)^2 = \left(2 \varphi + 1\right)^2 = 4 \varphi^2 + 4\varphi + 1 = 8\varphi^2-3\)이며, -3을 1,000,000,007로 나눈 나머지는 1,000,000,004이므로, 위와 같은 출력이 나온다.
www.acmicpc.net
%2022. 1. 15. 05:08에 작성된 글입니다%