本文主要是介绍hdu 3802 Ipad,IPhone，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目： Ipad,IPhone
思路：这题。。。好坑反正，WA了刚好20次。。。
题目给的式子，分成两部分，对于第一部分，直接快速幂即可，对于后面的部分，后面括号里是整数的证明 出题人 AekdyCoin 用二次剩余进行了解说，请点击 here
对于后面的部分，是不是整数我给直接忽略了。。。不然怎么进行取余呢。。事实证明，前半部分是有存在感的，根据欧拉准则，即二次剩余的欧拉判别法 ，我们知道a是模p的二次剩余时a^((p-1)/2)=1(mod p)，非二次剩余时，a^((p-1)/2)=-1(mod p) ，所以二次剩余时，前半部分的解为4，而非二次剩余的时候，前面的解为0，同时后半部分也不会有整数解，因此前半部分的存在时很有必要的。
好吧，继续说后半部分，既然是整数可以进行取余了，指数部分是菲波那契数列数列，可以构造矩阵这个不难，同时要用指数循环节进行优化，不然很容易溢出，然后就跪了。这里对素数p进行取余，所以指数部分，我们对其欧拉值进行取余，也就是对p-1取余得到斐波那契取余项。
然后再构造矩阵：
然后。。。因为矩阵初始化的时候忘了对2*(a+b),-(a+b)^2等进行取余，WA了差不多20次吧。。。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
typedef __int64 LL;
LL mod;
struct Matrix
{LL m[3][3];
}E,D;
LL a,b,n;
void init()
{for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)E.m[i][j]=(i==j);D.m[1][1]=1;D.m[1][2]=1;D.m[2][1]=1;D.m[2][2]=0;
}
Matrix Multi(Matrix A,Matrix B)
{Matrix ans;for(int i=1;i<=2;i++)for(int j=1;j<=2;j++){ans.m[i][j]=0;for(int k=1;k<=2;k++)ans.m[i][j]=(ans.m[i][j]+A.m[i][k]*B.m[k][j])%mod;}return ans;
}
Matrix Pow(Matrix A,LL k)
{Matrix ans=E;while(k){if(k&1){k--;ans=Multi(ans,A);}else{k/=2;A=Multi(A,A);}}return ans;
}
LL Fib(LL n)
{if(n==0)return 1;Matrix ans=Pow(D,n);return ans.m[1][1]%mod;
}
void Print(Matrix A)
{for(int i=1;i<=2;i++){for(int j=1;j<=2;j++)cout<<A.m[i][j]<<" ";cout<<endl;}
}
LL get(Matrix A,Matrix B,LL fib)
{Matrix ans=Pow(A,fib-1);ans=Multi(ans,B);return ans.m[1][1];
}
LL Pow(LL a,LL b)
{LL ans=1;while(b){if(b&1){b--;ans=(ans*a)%mod;}else{b/=2;a=(a*a)%mod;}}return ans;
}
int main()
{init();int t;cin>>t;init();while(t--){cin>>a>>b>>n>>mod;LL aa=(1+Pow(a,(mod-1)/2))%mod;LL bb=(1+Pow(b,(mod-1)/2))%mod;if(aa==0||bb==0){cout<<0<<endl;continue;}Matrix T,cnt;T.m[1][1]=2*(a+b)%mod;T.m[1][2]=-(a-b)*(a-b)%mod;T.m[2][1]=1;T.m[2][2]=0;cnt.m[1][1]=2*(a+b)%mod;cnt.m[2][1]=2;LL tmp;mod--;tmp=Fib(n);mod++;LL ans=get(T,cnt,tmp);ans=4*ans%mod;if(ans<0)ans+=mod;cout<<ans<<endl;}return 0;
}
这篇关于hdu 3802 Ipad,IPhone的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
