首页 > 代码库 > HDU 3221

HDU 3221

2024-07-20 11:22:07   209人阅读

不知道哪里错了，测试了几十组数据均正确。。。

可以找出规律，指数的增长是兔子数列。这个数列，是可以用矩阵快速幂得到的，见POJ 3070

然后，竟然有一条公式：

 A^B%C = A^(B%phi(C)+phi(C))%C

然后就可以求解了

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;struct Matrax {	long long m[2][2];};Matrax at,per;long long M;void initial(){	long long i,j;	for(i=0;i<2;i++)	for(j=0;j<2;j++)	per.m[i][j]=(i==j);	at.m[0][0]=at.m[0][1]=at.m[1][0]=1;	at.m[1][1]=0;}Matrax multi(Matrax a,Matrax b){	Matrax c;	for(int i=0;i<2;i++){		for(int j=0;j<2;j++){			c.m[i][j]=0;			for(int k=0;k<2;k++)			c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%M;			c.m[i][j]%=M;		}	}	return c;}long long Power(int k){	Matrax c,p,ans=per;	p=at;	while(k){		if(k&1){			ans=multi(ans,p);			k--;		}		else{			k/=2;			p=multi(p,p);		}	}	return ans.m[1][0]%M;}long long Euler(long long n){	long long rea=n;	for(long long  i=2;i*i<=n;i++){		if(n%i==0){			rea=rea-rea/i;			do{				n/=i;			}while(n%i==0);		}	}	if(n>1)	rea=rea-rea/n;	return rea;}long long quick(long long a,long long b,long long m){	long long ans=1;	a%=m;	while(b){		if(b&1){			ans=(ans*a)%m;		}		b>>=1;		a=(a*a)%m;	}	return ans;}int main ( ){	long long a,b,n,p;	int t;	int kase=0;	scanf("%d",&t);	initial();	while(t--){		cin>>a>>b>>p>>n;	/*	if(a==0&&b==0){			printf("Case #%d: 0\n",++kase);			continue;		}*/		M=Euler(p);		long long bs,as;		if(n==1){			bs=0%M; as=1%M;		}		else if(n==2){			bs=1%M; as=0%M;		}		else{			bs=Power(n-1)%M;			as=Power(n-2)%M;		}		long long tb=quick(b,bs+M,p)%p;		long long ta=quick(a,as+M,p)%p;		printf("Case #%d: %lld\n",++kase,(tb*ta)%p);	}	return 0;}

　　

COPY 别人的代码粘在这里

#include <stdio.h>#define MAXN 1000002typedef struct{    long long m[2][2];}Matrix;int mod;int a,b;int phi[MAXN+5];int fib[50];void PHI(){    int i,k;    for (i=2;i<MAXN;i++)    {        phi[i]=i;    }    for (i=2;i<MAXN;i++)    {        if (phi[i]!=i) continue;        k=1;        while(k*i<MAXN)        {            phi[i*k]=phi[i*k]/i*(i-1);            k++;        }    }}long long Fpow(long long t,int n){    long long ret=1;    while(n)    {        if (n&1) ret=(ret*t)%mod;        n>>=1;        t=(t*t)%mod;    }    return ret;}Matrix Mul(Matrix a,Matrix b,int p){    int i,j,k;    Matrix c;    for (i=0;i<2;i++)    {        for (j=0;j<2;j++)        {            c.m[i][j]=0;            for (k=0;k<2;k++)            {                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%p;            }        }    }    return c;}long long CountFib(int n,int p){    int i;    Matrix a,b;    a.m[0][0]=a.m[0][1]=a.m[1][0]=b.m[0][0]=1;    a.m[1][1]=b.m[1][0]=0;    while(n)    {        if (n&1) b=Mul(a,b,p);        a=Mul(a,a,p);        n>>=1;    }    return b.m[0][0];}long long Power(int t,int n){    int i;    int p=phi[mod];    fib[0]=fib[1]=1;    for (i=2;i<=n;i++)    {        fib[i]=fib[i-1]+fib[i-2];        if (fib[i]>=p) break;    }    if (i>n)    {        return Fpow(t,fib[n]);    }    int f=CountFib(n,p)+p;    return Fpow(t,f);}int main(){    int i,j,cnt=1,T,n;    long long ans;    PHI();    scanf("%d",&T);    while(T--)    {        scanf("%d%d%d%d",&a,&b,&mod,&n);        printf("Case #%d: ",cnt++);        if (n==1)        {            printf("%d\n",a%mod);            continue;        }        if (n==2)        {            printf("%d\n",b%mod);            continue;        }        if (a==0 || b==0)        {            printf("0\n");            continue;        }        if (mod==1)        {            printf("0\n");            continue;        }        ans=(Power(a,n-3)*Power(b,n-2))%mod;        printf("%I64d\n",ans);    }    return 0;}

　　

HDU 3221


联系
我们