BZOJ 1409 Password 矩阵乘法+线性筛
来源：程序员人生 发布时间：2015-03-25 11:36:42 阅读次数：3633次
题目大意：求p^F[n] mod q 其中F是斐波那契数列，p是质数，q<p
由于pq互质因此可以套用欧拉定理
然后就是矩乘求斐波那契的事情了- -
垃圾题卡O(√q) 求Phi的时候要枚举质数 不能1个1个枚举
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const long long empty[2][2]={{0,0},{0,0}};
const long long I[2][2]={{1,0},{0,1}};
const long long trans[2][2]={{0,1},{1,1}};
int n,p,q,mod;
int prime[100100],tot;
bool not_prime[100100];
namespace Matrix_Multiplication{
struct Matrix{
long long xx[2][2];
Matrix(const long long _[2][2])
{
memcpy(xx,_,sizeof xx);
}
long long* operator [] (int x)
{
return xx[x];
}
friend void operator *= (Matrix &x,Matrix y)
{
int i,j,k;
Matrix z(empty);
for(i=0;i<2;i++)
for(j=0;j<2;j++)
for(k=0;k<2;k++)
(z[i][j]+=x[i][k]*y[k][j])%=mod;
x=z;
}
};
Matrix Quick_Power(Matrix x,int y)
{
Matrix re(I);
while(y)
{
if(y&1) re*=x;
x*=x; y>>=1;
}
return re;
}
}
void Linear_Shaker()
{
int i,j;
for(i=2;i<=100000;i++)
{
if(!not_prime[i])
prime[++tot]=i;
for(j=1;prime[j]*i<=100000;j++)
{
not_prime[prime[j]*i]=true;
if(i%prime[j]==0)
break;
}
}
}
int Phi(int x)
{
int i,re=x;
for(i=1;(long long)prime[i]*prime[i]<=x;i++)
if(x%prime[i]==0)
{
re/=prime[i];re*=prime[i]⑴;
while(x%prime[i]==0)
x/=prime[i];
}
if(x!=1) re/=x,re*=x⑴;
return re;
}
int Quick_Power(long long x,int y)
{
long long re=1;
while(y)
{
if(y&1) (re*=x)%=q;
(x*=x)%=q; y>>=1;
}
return re;
}
int main()
{
using namespace Matrix_Multiplication;
int T;
Linear_Shaker();
for(cin>>T>>p;T;T--)
{
scanf("%d%d",&n,&q);
mod=Phi(q);
int ans=Quick_Power(trans,n)[1][0];
printf("%d
",(int)Quick_Power(p,ans)%q);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
