Password

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

题目描述

  1. Rivest是密码学专家。近日他正在研究一种数列E = {E[1],E[2],……,E[n]},
  2. E[1] = E[2] = pp为一个质数),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

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #define maxn 1000005
  5. using namespace std;
  6. int m,p,n,q,mo;
  7. int phi[maxn+4],prime[maxn];
  8. bool vis[maxn+4];
  9. void pre()
  10. {
  11. int k=0;
  12. phi[1]=1;
  13. for(int i=2;i<=maxn;i++)
  14. {
  15. if(vis[i]==0)
  16. {
  17. phi[i]=i-1;
  18. prime[++k]=i;
  19. }
  20. for(int j=1;j<=k;j++)
  21. {
  22. if(prime[j]*i>maxn) break;
  23. vis[prime[j]*i]=1;
  24. if(i%prime[j]==0)
  25. {
  26. phi[i*prime[j]]=phi[i]*prime[j];
  27. break;
  28. }
  29. else phi[i*prime[j]]=phi[i]*(prime[j]-1);
  30. }
  31. }
  32. }
  33. int getphi(int t)
  34. {
  35. int kk=t;
  36. for(int i=2;i*i<=t;i++)
  37. if(t%i==0)
  38. {
  39. kk=kk-kk/i;
  40. while(t%i==0)
  41. t/=i;
  42. }
  43. if(t>1)
  44. kk=kk-kk/t;
  45. return kk;
  46. }
  47. struct mat
  48. {
  49. long long a[5][5];
  50. }b,c,f;
  51. void init()
  52. {
  53. memset(b.a,0,sizeof(b.a));
  54. memset(c.a,0,sizeof(c.a));
  55. memset(f.a,0,sizeof(f.a));
  56. c.a[1][1]=1;c.a[1][2]=1;c.a[2][1]=1;c.a[2][2]=0;
  57. f.a[1][1]=1;f.a[1][2]=1;
  58. b.a[1][1]=1;b.a[2][2]=1;
  59. }
  60. mat operator *(mat A,mat B)
  61. {
  62. mat z={0};
  63. for(int i=1;i<=2;i++)
  64. for(int j=1;j<=2;j++)
  65. for(int k=1;k<=2;k++)
  66. z.a[i][j]+=(A.a[i][k]%mo*B.a[k][j]%mo)%mo;
  67. return z;
  68. }
  69. int main()
  70. {
  71. pre();
  72. scanf("%d%d",&m,&p);
  73. long long t,ans=1,mod;
  74. while(m--)
  75. {
  76. scanf("%d%d",&n,&q);
  77. init();n=n-1;
  78. if(q<=maxn) mo=phi[q];
  79. else mo=getphi(q);
  80. if(n>=2)
  81. {
  82. while(n)
  83. {
  84. if(n&1) b=b*c;
  85. c=c*c;
  86. n>>=1;
  87. }
  88. f=f*b;
  89. }
  90. t=f.a[1][2]%mo;
  91. mod=p;ans=1;
  92. if(t!=0)
  93. while(t)
  94. {
  95. if(t&1) ans=(ans%q*mod)%q;
  96. mod=mod%q*mod%q;
  97. t>>=1;
  98. }
  99. else ans=1%q;
  100. printf("%lld\n",ans);
  101. }
  102. return 0;
  103. }

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

发表评论

表情:
评论列表 (有 0 条评论,277人围观)

还没有评论,来说两句吧...

相关阅读

    相关 Password

    题目描述 Rivest是密码学专家。近日他正在研究一种数列E = {E[1],E[2],……,E[n]}, 且E[1] = E[2] = p(p为一个质数