Hdu 3221 Brute-force Algorithm (矩阵欧拉定理降幂)

Bertha 。 2022-09-17 12:19 141阅读 0赞

利用迭代思想，最后推得的规律和Hdu4549一样，我的Hdu4549题解：http://blog.csdn.net/whyorwhnt/article/details/12858485

本题与Hdu4549的不同点在于模值不一定为素数，所以利用欧拉定理来降幂

[欧拉定理 (数论) - 维基百科，自由的百科全书][_ -]

关于降幂公式的证明：[【关于 A^x = A^(x % Phi(C) + Phi(C)) (mod C) 的若干证明】【指数循环节】\_AekdyCoin的空间\_百度空间][A_x _ A_x _ Phi_C_ _ Phi_C_ _mod C_ _AekdyCoin]

![SouthEast][]

#include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    #define i64 __int64
    
    i64 mod,modd,phi;
    const int N=2;
    
    class Matrix
    {
    public:
    	i64 a[N][N];
    	int n;   //矩阵大小
    
    	void init (int x)
    	{
    		memset(a,0,sizeof(a));
    		if (x) for (int i=0;i<N;i++)
    			a[i][i]=1;
        }
    
    	Matrix operator * (Matrix b)
    	{
    		Matrix p;
    		p.n=b.n;   //
    		p.init(0);
    		for (int i=0;i<n;i++) for (int j=0;j<n;j++)
    			for (int k=0;k<n;k++)
    				(p.a[i][j]+=a[i][k]*b.a[k][j]%modd)%=modd;
    		return p;
    	}
    
    	Matrix power (int t)
    	{
    		Matrix ans,p=*this;
    		ans.n=p.n;  //
    		ans.init(1);
    		while (t)
    		{
    			if (t&1) ans=ans*p;
    			p=p*p;
    			t>>=1;
    		}
    		return ans;
    	}
    }a;
    
    __int64 modPow (__int64 s,__int64 index,__int64 mod)
    //蒙哥马利幂模算法  
    //快速幂  
    //返回值(s^index)%mod  
    {    
        __int64 ans=1;    
        s%=mod;    
        while (index>=1)    
        {    
            if ((index&1)==1)   //奇数    
                ans=(ans*s)%mod;    
            index>>=1;    
            s=s*s%mod;    
        }    
        return ans;    
    }  
    
    i64 Euler (i64 n)
    {
        i64 i,ans=n;
        for (i=2;i*i<=n;i++) if (n%i==0)
        {
            ans=ans/i*(i-1);
            while (n%i==0) n/=i;
        }
        if (n>1) ans=ans/n*(n-1);
        return ans;
    }
    
    void Deal (int n)
    {//注意矩阵快速幂的模用的是modd,即mod-1;
    	a.init(0);
    	a.n=2;
    	a.a[0][0]=1,a.a[0][1]=1;
    	a.a[1][0]=1,a.a[1][1]=0;
    	a=a.power(n-2);
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	int T;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		i64 k,t,n;
    		scanf("%I64d%I64d%I64d%I64d",&k,&t,&mod,&n);
    		n--;                ///
    		phi=Euler(mod);
    		modd=phi;
    		printf("Case #%d: ",Cas);
    		if (n==0)
    		{
    			printf("%I64d\n",k%mod);
    			continue;
    		}
    		else if (n==1)
    		{
    			printf("%I64d\n",t%mod);
    			continue;
    		}
    		else if (n==2)
    		{
    			printf("%I64d\n",k*t%mod);
    			continue;
    		}
    		else
    		{
    			Deal (n);
    			i64 index1=a.a[1][0]+a.a[1][1];  //a的次数
    			if (index1>=phi)
    				index1=index1%phi+phi;
    			i64 index2=a.a[0][0]+a.a[0][1];  //b的次数
    			if (index2>=phi)
    				index2=index2%phi+phi;
    
    			i64 res=modPow(k,index1,mod);
    			res=(res*modPow(t,index2,mod))%mod;
    			printf("%I64d\n",res);
    		}
    	}
    	return 0;
    }

[_ -]: http://zh.wikipedia.org/wiki/%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86_%28%E6%95%B0%E8%AE%BA%29
[A_x _ A_x _ Phi_C_ _ Phi_C_ _mod C_ _AekdyCoin]: http://hi.baidu.com/aekdycoin/item/e493adc9a7c0870bad092fd9
[SouthEast]: /images/20220828/1174b1eb9c32479b82bb1ff7becb0bb4.png