Password_综合

问题 A: Password

时间限制: 1 Sec 内存限制: 64 MB
提交: 55 解决: 35

题目描述

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

样例输入

样例输出

输出样例1
3
1输出样例2
3
0
1
1

Password：
算法分析:矩阵乘法+线性筛
E[i]=p^f[i]
f[i]表示斐波那契数列的第i项
E[i]%q
=p^f[i]%q
因为q<p，所以gcd(p,q)=1
所以p^phi(q)%q=1，注意q不一定是质数
先求f[i]%phi(q)的值，再用快速幂求值即可
其实题目就是求p^F[n]  发现p,q互质，于是我们开心的大力用欧拉函数和矩阵快速幂


  
   #include<iostream>
  
  
   #include<cmath>
  
  
   #include<cstring>
  
  
   #include<cstdio>
  
  
   #include<queue>
  
  
   #include<map>
  
  
   #include<cstdlib>
  
  
   #include<algorithm>
  
  
   //#define V 
  
  
   //#define mod 1000000007
  
  
   #define LL long long
  
  
   using 
   namespace 
   std;
  
  
   LL p,n,q,t;
  
  
   LL s[100+(1<<16)],nd;
   //,d[(1<<16)+100];
  
  
   bool 
   sd[(1<<16)+100];
  
  
   LL g,mod;
  
  
   struct 
   mat
  
  
   {
    
  
  
    
   LL m[5][5];
  
  
      
   mat()
  
  
      
   {
    
  
  
        
   memset
   (m,0,
   sizeof
   (m));     
  
  
      
   }       
  
  
   };
  
  
   inline 
   mat mul(mat &aa,mat &b,
   int 
   mod)
  
  
   {
    
  
  
       
   mat c;
  
  
       
   for
   (
   int 
   i=1;i<=2;i++)
  
  
        
   for
   (
   int 
   j=1;j<=2;j++)
  
  
        
   {
    
  
  
         
   c.m[i][j]=0;
  
  
         
   for
   (
   int 
   k=1;k<=2;k++)        
  
  
              
   c.m[i][j]+=(aa.m[i][k]*b.m[k][j])%mod;
   //cout<<c.m[i][j]<<"  @@@##"<<endl;
  
  
              
   c.m[i][j]%=mod;
  
  
         
   }
  
  
      
   return 
   c; 
  
  
   }
  
  
   inline 
   mat init()
  
  
   {
    
  
  
               
   mat res;
  
  
               
   res.m[1][1]=1;
  
  
               
   res.m[1][2]=0;
  
  
               
   res.m[2][1]=0;
  
  
               
   res.m[2][2]=1;
  
  
               
   return 
   res;
  
  
             
  
  
   }
  
  
   inline 
   LL ks(mat aa,LL k,
   int 
   mod)
  
  
   {
    
  
  
       
   mat res=init();
  
  
       
   while
   (k)
  
  
       
   {
    
  
  
         
   if
   (k&1)
  
  
         
   res=mul(res,aa,mod);
  
  
          
   k>>=1;
  
  
        
   aa=mul(aa,aa,mod);
  
  
       
   }
  
  
       
   return 
   res.m[1][1];
  
  
   }
  
  
  
   inline 
   void 
   pow
   ()
  
  
   {
    
  
  
          
   //cout<<(1<<16)<<endl;
  
  
        
   sd[0]=sd[1]=1;
  
  
        
   for
   (
   int 
   i=2;i<(1<<16);i++)
  
  
        
   {
    
  
  
           
   //cout<<i<<endl;
  
  
           
   if
   (!sd[i])        
  
  
           
   {
    
  
  
            
   s[++nd]=i;
  
  
   //         d[i]=i-1;
  
  
           
   } 
   //cout<<i<<endl;                  
  
  
           
   for
   (
   int 
   j=1;j<=nd&&i*s[j]<=(1<<16);j++)
  
  
           
   {   
   // cout<<i<<endl; 
  
  
               
   sd[i*s[j]]=1; 
  
  
               
   if
   (!(i%s[j]))
  
  
               
   break
   ;          
  
  
           
   }                     
  
  
        
   }  
  
  
   }
  
  
   inline 
   void 
   ps(LL x)
  
  
   {
    
  
  
     
   g=1;
  
  
     
   LL ww=x;
  
  
     
   //int ff=0;
  
  
     
   for
   (
   int 
   i=1;i<=nd;i++)
  
  
     
   if
   (x==1)
   break
   ;
  
  
     
   else 
   if
   (x%s[i]==0)
  
  
     
   {
    
  
  
         
   // ff=1;
  
  
          
   g*=s[i]-1;
  
  
          
   x/=s[i];
  
  
        
   while
   (x%s[i]==0)
  
  
        
   {
    
  
  
          
   g*=s[i]; 
  
  
          
   //if(ww==411518)
  
  
          
   //cout<<g<<"  **"<<x<<"  "<<s[i]<<endl; 
  
  
          
   x/=s[i];               
  
  
        
   }    
  
  
        
   //if(ww==411518)
  
  
        
   //cout<<g<<"  **"<<x<<"  "<<s[i]<<endl; 
  
  
    
   }   
  
  
    
   if
   (x!=1)g*=x-1; 
  
  
    
   //cout<<g<<" @@#$"<<endl;    
  
  
   }
  
  
   inline 
   LL pp(LL x,LL y)
  
  
   {
    
  
  
      
   LL w=1;
  
  
      
   for
   (;y;y>>=1,x=(LL)x*x%mod)
  
  
        
   if
   (y&1)w=(LL)w*x%mod;
  
  
        
   return 
   w;      
  
  
           
  
  
   }
  
  
   inline 
   int 
   haha()
  
  
   {
    
  
  
        
   //freopen("in.txt","r",stdin);freopen("out.txt","w",stdout); //
  
  
        
   //freopen("password.in","r",stdin); freopen("password.out","w",stdout);
  
  
       
   cin>>t>>p;
  
  
      
   // cout<<" !! "<<endl;
  
  
        
   int 
   ds;
  
  
        
   pow
   ();
  
  
        
   mat a;
  
  
         
   a.m[1][1]=1;
  
  
         
   a.m[1][2]=1;
  
  
         
   a.m[2][1]=1;
  
  
         
   a.m[2][2]=0;
  
  
        
   while
   (t--)
  
  
        
   {
    
  
  
          
   scanf
   (
   "%d%d"
   ,&n,&q);
  
  
          
   if
   (q==1)
  
  
          
   {
    
  
  
             
   printf
   (
   "0\n"
   );
   continue
   ;        
  
  
          
   }
  
  
          
   g=0;  
  
  
         
   ps(q); 
  
  
         
   mod=g;
  
  
         
   n--;
  
  
         
   ds=ks(a,n,g); 
  
  
        
   // cout<<g<<"  "<<ds<<"  "<<q<<endl; 
  
  
         
   mod=q; 
  
  
         
   printf
   (
   "%d\n"
   ,pp(p,ds));
  
  
          
   //while()        
  
  
        
   } 
  
  
   }
  
  
   int 
   gg=haha();
  
  
   int 
   main()
  
  
   {;}