[关闭]
@ysner 2018-10-03T10:54:33.000000Z 字数 2600 阅读 2136

BSGS算法及拓展

总结 数论 BSGS


定义

一种用来求解高次同余方程的算法。
一般问题形式:求使得的最小非负

算法

要求是质数。
由费马小定理可知,,所以暴力枚举只要枚举到即可。
但是由于一般都很大,所以一般都跑不动。。。

优化算法
现在令(其中)。
则方程可化为,

然后可以发现(否则就是负数)
所以我们可以暴力枚举,与所得的存在哈希表里,然后再暴力枚举,最后得出结果。

还要注意一些边界:

一道Poj上的板子题
[SDOI2011]计算器

  1. struct Hash_Table
  2. {
  3. int h[N],cnt;
  4. struct Edge{int u,v,nxt;}e[N*10];
  5. il void clear(){memset(h,-1,sizeof(h));cnt=0;}
  6. il void add(re int u,re int v,re int w){e[++cnt]=(Edge){w,v,h[u]};h[u]=cnt;}
  7. il int Query(re int x)
  8. {
  9. re int t=x%mod;
  10. for(re int i=h[t];i+1;i=e[i].nxt)
  11. if(e[i].u==x) return e[i].v;
  12. return -1;
  13. }
  14. il void solve(re int y,re int z,re int p)
  15. {
  16. y%=p;z%=p;
  17. if(!y) {puts("no solution");return;}
  18. if(z==1) {puts("0");return;}
  19. re int m=sqrt(p)+1;clear();
  20. for(re int i=0,t=z;i<m;++i,t=1ll*t*y%p) add(t%mod,i,t);
  21. for(re int i=1,tt=ksm(y,m,p),t=tt;i<=m+1;++i,t=1ll*t*tt%p)
  22. {
  23. re int j=Query(t);if(j==-1) continue;
  24. printf("%d\n",i*m-j);return;
  25. }
  26. puts("no solution");
  27. }
  28. }BSGS;
  29. int main()
  30. {
  31. re int y,p,z;
  32. while(scanf("%d%d%d",&p,&y,&z)!=EOF)
  33. {
  34. BSGS.solve(y,z,p);
  35. }
  36. return 0;
  37. }

拓展算法

不要求是质数。
那就说明很可能,不满足费马小定理。
费马小定理提供了枚举上限,没有它这种问题就不好做了。。。

想想怎么把约分。

把方程改写成等式形式:


分析一下,可以发现一定是的倍数。
:

接下来再次检查是否为,若否,说明还可以继续约分,理由同上。

最后形式为(那个反正是个正整数)

注意边界:

咕谷模板题

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #define il inline
  8. #define re register
  9. #define ll long long
  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. il ll ksm(re ll S,re ll n,re int p)
  15. {
  16. re ll T=S;S=1;
  17. while(n)
  18. {
  19. if(n&1) S=S*T%p;
  20. T=T*T%p;
  21. n>>=1;
  22. }
  23. return S;
  24. }
  25. struct Hash_Table
  26. {
  27. int h[N],cnt;
  28. struct Edge{int u,v,nxt;}e[N*10];
  29. il void clear(){memset(h,-1,sizeof(h));cnt=0;}
  30. il void add(re int u,re int v,re int w){e[++cnt]=(Edge){w,v,h[u]};h[u]=cnt;}
  31. il int Query(re int x)
  32. {
  33. re int t=x%mod;
  34. for(re int i=h[t];i+1;i=e[i].nxt)
  35. if(e[i].u==x) return e[i].v;
  36. return -1;
  37. }
  38. il void solve(re int y,re int z,re int p)
  39. {
  40. if(z==1) {puts("0");return;}
  41. re int k=0,a=1;
  42. while(233)
  43. {
  44. re int t=__gcd(y,p);if(t==1) break;
  45. if(z%t) {puts("No Solution");return;}
  46. z/=t;p/=t;++k;a=1ll*a*y/t%p;
  47. if(z==a) {printf("%d\n",k);return;}//有意思的地方
  48. }
  49. re int m=sqrt(p)+1;clear();
  50. for(re int i=0,t=z;i<m;++i,t=1ll*t*y%p) add(t%mod,i,t);
  51. for(re int i=1,tt=ksm(y,m,p),t=1ll*a*tt%p;i<=m+1;++i,t=1ll*t*tt%p)
  52. {
  53. re int j=Query(t);if(j==-1) continue;
  54. printf("%d\n",i*m-j+k);return;
  55. }
  56. puts("No Solution");
  57. }
  58. }BSGS;
  59. int main()
  60. {
  61. re int y,p,z;
  62. while(scanf("%d%d%d",&y,&p,&z))
  63. {
  64. if(!p&&!y&&!z) break;
  65. BSGS.solve(y,z,p);
  66. }
  67. return 0;
  68. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注