【NOIP模拟赛】一道挖掉背景的数学题【NOIP模拟赛】一道挖掉背景的

Title:【Empty】 Time Limit：1000 ms
Memory Limit：131072 KBytes
Description 给定n与p,求\(\left\lfloor x^n\right\rfloor \% p\),x=\(\frac{\sqrt{5}+1}{2}\)。
Input Format 输入一行，两个非负整数n,p。
Output Format 输出一个整数，表示答案
Sample Input 5 97
Sample Output 11
Solution 今天写道数学题吧OwO
这道题我们看到\(\frac{{\sqrt 5 {\rm{ + }}1}}{2}\)，那么我们容易想到另一个无理数\(\frac{1-\sqrt 5}{2}\)对吧？
因为这两个无理数是方程\(t^2-t-1=0\)的两根
那么数学好的大佬肯定一眼看出这个特征方程对应的递推通式是\(f[i]=f[i-1]+f[i-2]\)
我们首先设\(x1=\frac{{\sqrt 5 {\rm{ + }}1}}{2}\)，\(x2=\frac{1-\sqrt 5}{2}\)
那么其实这个递推式的通式其实就是\(f[n]=c1*x1^n+c2*x2^n\)
【【NOIP模拟赛】一道挖掉背景的数学题】具体这个递推式是什么呢？我们并不在乎对吧（引用：我又不是数学老师）
为了得到\(x1^n\)，我们不妨假设这个递推式的通项式为\(f[n]=(\frac{{\sqrt 5 {\rm{ + }}1}}{2})^n+(\frac{1-\sqrt 5}{2})^n\)
首先我们将0,1带入递推通式得到\(f_0=2,f_1=1\)，那么我们所得到的递推式每一项都必然是一个整数
由于\(-1<\frac{1-\sqrt 5}{2}<0\)，显然\(\begin{cases} -1<(\frac{1-\sqrt 5}{2})^n<0& \text{n%2==1} \\ 0<(\frac{1-\sqrt 5}{2})^n<1& \text{n%2==0} \end{cases}\)
那么我们只要对于n的奇偶性讨论一下，如果是奇就直接输出\(f[n]\)，否则输出\(f[n]-1\)
剩下就是一个矩阵乘法求递推第n项，因此很容易求解

#include long long n; int zqm,f0,f1; struct r{ int a,b,c,d; }a,c; r operator *(r a,r b){ r c; c.a=(a.a*1ll*b.a+a.b*1ll*b.c)%zqm; c.b=(a.a*1ll*b.b+a.b*1ll*b.d)%zqm; c.c=(a.c*1ll*b.a+a.d*1ll*b.c)%zqm; c.d=(a.c*1ll*b.b+a.d*1ll*b.d)%zqm; return c; } int main() { scanf("%lld%d",&n,&zqm); f0=2,f1=1; if (n==0){ printf("%d\n",1%zqm); return 0; } if (n==1){ printf("%d\n",1%zqm); return 0; } n-=2; int ans=0; if (!(n&1)) ans--; a=(r){1,1,1,0}; c=a; while (n){ if ((n&1)) c=c*a; a=a*a,n>>=1; } ans=(c.a*1ll*f1+f0*1ll*c.b+ans)%zqm; printf("%d",ans); return 0; }

转载于:https://www.cnblogs.com/Cool-Angel/p/7800948.html