Sequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1424 Accepted Submission(s): 469
Problem Description
Holion
August will eat every thing he has found.
Now there are many foods,but he does not want to eat all of them at once,so he find a sequence.
fn=⎧⎩⎨⎪⎪1,ab,abfcn−1fn−2,n=1n=2otherwise
He gives you 5 numbers n,a,b,c,p,and he will eat fn foods.But there are only p foods,so you should tell him fn mod p.
Now there are many foods,but he does not want to eat all of them at once,so he find a sequence.
fn=⎧⎩⎨⎪⎪1,ab,abfcn−1fn−2,n=1n=2otherwise
He gives you 5 numbers n,a,b,c,p,and he will eat fn foods.But there are only p foods,so you should tell him fn mod p.
Input
The
first line has a number,T,means testcase.
Each testcase has 5 numbers,including n,a,b,c,p in a line.
1≤T≤10,1≤n≤1018,1≤a,b,c≤109,p is a prime number,and p≤109+7.
Each testcase has 5 numbers,including n,a,b,c,p in a line.
1≤T≤10,1≤n≤1018,1≤a,b,c≤109,p is a prime number,and p≤109+7.
Output
Output
one number for each case,which is fn mod
p.
Sample Input
1
5 3 3 3 233
Sample Output
190
网上题解解释起来不是非常清楚，我想了一节课终于明白了为什么要对p-1取模了。
首先理解费马小定理：若a与p互质且b为素数，则a^(p-1)%p恒为1。但是这跟题目有啥关系？所以要先推题目的递推式
先两边取loga对数（刚开始取log10，发现化不出来）然后就可以得到。
因此另。即
。然后求Kn。
（右上角的1与右下边的b互换不影响结果）
然后此题数据有点水，若a为p的倍数（a=x*p），此时原式可以为((x*p)^Kn)%p=0，因此要特判为0，不然结果会是1，由于后台数据并没有考虑这个情况，因此部分人没考虑这个情况直接模p-1也是可以过的，就是这个地方让我纠结了很久：虽然p为素数与绝大部分数都互质，但万一a是p的倍数怎么办？至此得出答案。
代码：
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define MM(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long LL;
LL n,a,b,c,p;
struct mat
{
LL pos[3][3];
mat (){MM(pos);}
};
inline mat operator*(const mat &a,const mat &b)
{
mat c;
for (int i=0; i<3; i++)
{
for (int j=0; j<3; j++)
{
for (int k=0; k<3; k++)
c.pos[i][j]+=(a.pos[i][k]*b.pos[k][j])%(p-1);
}
}
return c;
}
inline mat operator^(mat a,LL b)
{
mat r,bas=a;
for (int i=0; i<3; i++)
r.pos[i][i]=1;
while (b!=0)
{
if(b&1)
r=r*bas;
bas=bas*bas;
b>>=1;
}
return r;
}
inline LL qpow(LL a,LL b)
{
LL r=1,bas=a;
while (b!=0)
{
if(b&1)
r=(r*bas)%p;
bas=(bas*bas)%p;
b>>=1;
}
return r%p;
}
int main(void)
{
int tcase,i,j;
scanf("%d",&tcase);
while (tcase--)
{
scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&p);
if(a%p==0)
puts("0");
else if(n==1)
puts("1");
else if(n==2)
printf("%lld
",qpow(a,b));
else
{
mat t,one;
t.pos[0][0]=c;t.pos[0][1]=1;t.pos[0][2]=b;
t.pos[1][0]=1;
t.pos[2][2]=1;
one.pos[0][0]=b;one.pos[1][0]=0;one.pos[2][0]=1;
t=t^(n-2);
one=t*one;
printf("%lld
",qpow(a,one.pos[0][0]));
}
}
return 0;
}