Password

小咪咪 2022-01-07 12:27 218阅读 0赞

## 题目描述 ##

Rivest是密码学专家。近日他正在研究一种数列E = {E[1],E[2],……,E[n]}，
    且E[1] = E[2] = p（p为一个质数），E[i] = E[i-2]*E[i-1] （若2<i<=n）。

例如\{2,2,4,8,32,256,8192,……\}就是p = 2的数列。在此基础上他又设计了一种加密算法，该算法可以通过一个密钥q (q < p)将一个正整数n加密成另外一个正整数d，计算公式为：d = E\[n\] mod q。现在Rivest想对一组数据进行加密，但他对程序设计不太感兴趣，请你帮助他设计一个数据加密程序。

## 输入 ##

第一行读入m，p。其中m表示数据个数，p用来生成数列E。 以下有m行，每行有2个整数n，q。n为待加密数据，q为密钥。 数据范围: 0 < p n< 2^31 0 < q < p 0 < m <= 5000。

## 输出 ##

将加密后的数据按顺序输出到文件 第i行输出第i个加密后的数据。 输入样例1 2 7 4 5 4 6 输入样例2 4 7 2 4 7 1 6 5 9 3

**考试打了一个快速幂，但斐波那契数列增长很快，最后能存到90项，其实和暴力没什么区别**

**这题用到了欧拉定理，a^b%p=a^(b%phi(p))%p;(phi(p)是p的欧拉函数)GCD(a,p)==1**

**扩展欧拉定理a^b%p=a^((b%phi(p))%p+phi(p)) %p;(GCD(a,p)>1)**

**适用范围不一样，这个一定要特别注意**

**矩阵快速幂求f的第n项，预处理phi（p），p很大的时候单独求，然后快速幂求ans**

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #define maxn 1000005
    using namespace std;
    int m,p,n,q,mo;
    int phi[maxn+4],prime[maxn];
    bool vis[maxn+4];
    void pre()
    {
         int k=0;
         phi[1]=1;
         for(int i=2;i<=maxn;i++)
         {
            if(vis[i]==0)
            {
              phi[i]=i-1;
              prime[++k]=i;          
            }
           for(int j=1;j<=k;j++)
           {
             if(prime[j]*i>maxn) break;      
             vis[prime[j]*i]=1;
             if(i%prime[j]==0) 
             {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
             }
             else  phi[i*prime[j]]=phi[i]*(prime[j]-1);
           }
         }   
    }
    int getphi(int t)
    {
          int kk=t;
          for(int i=2;i*i<=t;i++)
            if(t%i==0)
            {
                kk=kk-kk/i;
                while(t%i==0)
                    t/=i;
            }
            if(t>1)
                kk=kk-kk/t;
            return kk;
    }
    struct mat
    {
        long long a[5][5];   
    }b,c,f;
    void init()
    {
         memset(b.a,0,sizeof(b.a));
         memset(c.a,0,sizeof(c.a));
         memset(f.a,0,sizeof(f.a));
         c.a[1][1]=1;c.a[1][2]=1;c.a[2][1]=1;c.a[2][2]=0;
         f.a[1][1]=1;f.a[1][2]=1;
         b.a[1][1]=1;b.a[2][2]=1;
    }
    mat operator *(mat A,mat B)
    {
        mat z={0};
        for(int i=1;i<=2;i++)
         for(int j=1;j<=2;j++)
          for(int k=1;k<=2;k++)
            z.a[i][j]+=(A.a[i][k]%mo*B.a[k][j]%mo)%mo;
         
        return z;
    }
    int main()
    {
        pre();
        scanf("%d%d",&m,&p);
        long long t,ans=1,mod;
        while(m--)
        {
            scanf("%d%d",&n,&q);      
            init();n=n-1;
            if(q<=maxn) mo=phi[q];
            else mo=getphi(q);
            if(n>=2)
            {     
              while(n)
              {
                if(n&1) b=b*c;
                c=c*c;
                n>>=1; 
              }
              f=f*b;
            } 
            t=f.a[1][2]%mo;
            mod=p;ans=1;
            if(t!=0)
              while(t)
              {
               if(t&1) ans=(ans%q*mod)%q;   
               mod=mod%q*mod%q; 
               t>>=1;  
              }
            else ans=1%q;
            printf("%lld\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/hunterxhunterl/p/7780705.html