[关闭]
@ysner 2018-10-03T15:05:39.000000Z 字数 1900 阅读 2210

[SDOI2013]随机数生成器

BSGS 数论


题面

都过来看题解了,应该知道题面是什么吧

解析

好像还是模板题。
虽然说我不看标签还不一定能意识到要用bsgs

看到递推式之类的,应该要想到矩乘或者某些数学理论。。。
题目的问题矩乘处理不了。
也只能

设第天读到第页。
想想怎么把未知数弄到指数那里去。
数学必修五中常常给出递推式,要我们证一个玩意儿是等比数列。
这里要反其道而行。


解下方程发现其等比数列形式是:

那么

咦,是指数!

其中
然后套上模板就可以了。

显然的时候需要特判。
我在特判上栽了两次。。。

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  11. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  12. using namespace std;
  13. const int N=5e4,mod=45807;
  14. int T;
  15. int p,a,b,s,t,z,y;
  16. il int gi()
  17. {
  18. re int x=0,t=1;
  19. re char ch=getchar();
  20. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  21. if(ch=='-') t=-1,ch=getchar();
  22. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  23. return x*t;
  24. }
  25. il ll ksm(re ll S,re ll n)
  26. {
  27. re ll T=S;S=1;
  28. while(n)
  29. {
  30. if(n&1) S=S*T%p;
  31. T=T*T%p;
  32. n>>=1;
  33. }
  34. return S;
  35. }
  36. struct Hash_table
  37. {
  38. struct Edge{int u,v,nxt;}e[N*10];
  39. int h[N],cnt;
  40. il void clear(){memset(h,-1,sizeof(h));cnt=0;}
  41. il void add(re int u,re int v,re int w){e[++cnt]=(Edge){w,v,h[u]};h[u]=cnt;}
  42. il int Query(re int x)
  43. {
  44. for(re int i=h[x%mod];i+1;i=e[i].nxt)
  45. if(e[i].u==x) return e[i].v;
  46. return -1;
  47. }
  48. il void solve(re int y,re int z)
  49. {
  50. y%=p;z%=p;
  51. if(!y||!z) {puts("-1");return;}
  52. re int m=sqrt(p)+1;clear();
  53. for(re int i=0,t=z;i<m;++i,t=1ll*t*y%p) add(t%mod,i,t);
  54. for(re int i=1,tt=ksm(y,m),t=tt;i<=m;++i,t=1ll*tt*t%p)
  55. {
  56. re int j=Query(t);if(j==-1) continue;
  57. printf("%d\n",i*m-j+1);return;
  58. }
  59. puts("-1");
  60. }
  61. }BSGS;
  62. int main()
  63. {
  64. T=gi();
  65. while(T--)
  66. {
  67. p=gi();a=gi();b=gi();s=gi();t=gi();
  68. if(s==t) {puts("1");continue;}
  69. if(a==0)
  70. {
  71. if(b==t) puts("2");else puts("-1");//if(b==t) puts("1");????
  72. continue;
  73. }
  74. if(a==1)
  75. {
  76. if(b==0) puts("-1");
  77. else
  78. {
  79. re ll gu=1ll*(t+p-s)%p*ksm(b,p-2)%p;
  80. printf("%lld\n",gu+1);//printf("%lld\n",gu);????
  81. }
  82. continue;
  83. }
  84. re ll gu=1ll*b*ksm(a-1,p-2)%p;
  85. y=a;z=1ll*(t+gu)%p*ksm(s+gu,p-2)%p;
  86. BSGS.solve(y,z);
  87. }
  88. return 0;
  89. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注