前兩個操作都看出來做法了，第三個要用到BSGS這個算法

BSGS主要可以解 a^x=b(mod n)的 0<=x<n 的解

暫時先拿kb和hzwer的板子當黑盒吧。。數論細節短時間內沒有學的打算

upd:

學了一下BSGS算法的的理論以及這個板子的實現，似乎這個板子默認模數素數

模數不素的話用kb的吧，那個似乎是用前向星處理哈希沖突做的。。

#include<bits/stdc++.h> #include<stdio.h> #include<algorithm> #include<queue> #include<string.h> #include<iostream> #include<math.h> #include<set> #include<map> #include<vector> #include<iomanip> using namespace std; #define ll long long #define ull unsigned long long #define pb push_back #define FOR(a) for(int i=1;i<=a;i++) const int inf=0x3f3f3f3f; const ll Linf=9e18; const int maxn=1e5+7; const ll mod=100003; const double eps=1e-6;int gcd(int a,int b){return b==0?a:gcd(b,a%b);} void exgcd(int a,int b,int &x,int &y){if(b==0){x=1;y=0;return;}exgcd(b,a%b,x,y);int t=x;x=y;y=t-a/b*y; } int work1(ll y,int z,int p){y%=p;ll ans=1;for(int i=z;i;i>>=1,y=y*y%p)if(i&1)ans=ans*y%p;//printf("%d\n",ans);return ans; } void work2(int y,int z,int p){//xy+tp=z,求x最小正數解int g=gcd(y,p);if(z%g){puts("Orz, I cannot find x!");return;}y/=g;z/=g;p/=g;int a,b;exgcd(y,p,a,b);a=(ll)a*z%p;while(a<0)a+=p;printf("%d\n",a); } map<int,int>mp; void work3(int y,int z,int p){y%=p;if(!y&&!z){puts("1");return;}if(!y){puts("Orz, I cannot find x!");return;}mp.clear();ll m=ceil(sqrt(p)),t=1;mp[1]=m+1;for(ll i=1;i<m;i++){t=t*y%p;if(!mp[t])mp[t]=i;}ll tmp=work1(y,p-m-1,p),ine=1;for(ll k=0;k<m;k++){int i=mp[z*ine%p];if(i){if(i==m+1)i=0;printf("%lld\n",k*m+i);return;}ine=ine*tmp%p;}puts("Orz, I cannot find x!"); } int main(){int T,K;scanf("%d%d",&T,&K);for(int i=1;i<=T;i++){int y,z,p;scanf("%d%d%d",&y,&z,&p);if(K==1){int ans=work1(y,z,p);printf("%d\n",ans);}else if(K==2){work2(y,z,p);}else{work3(y,z,p);}} }

轉載于:https://www.cnblogs.com/Drenight/p/8611266.html

總結

以上是生活随笔為你收集整理的[SDOI2011]计算器 BSGS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。