「SPOJ 3105」Power Modulo Inverted
题目大意：
求关于 (x) 的方程
[a^x equiv b ;(mathrm{mod}; p)
]
的最小自然数解，不保证 (a,p) 互质
如果保证 (a,p) 互质，那么可以直接使用 ( exttt{BSGS}) 算法通过本题。
对于这道题目，我们考虑将式子变形
令 (t=gcd(a,p)),则有
[frac{a}{t}a^{x-1} equiv frac{b}{t} ;(mathrm{mod} ; frac{p}{t})
]
得到
[frac{a}{t} cdot a^{x-1} equiv b^{'} ;(mathrm{mod} ; p^{'})
]
(可以将其转换为等式，可能更好理解)
显然，当 (b ; mathrm{mod} ;t =0) 时可能有解，我们只需要按照这种方式已知递归求解，直至 (a^{'},p^{'}) 互质即可。
另外特别需要注意的是，最小自然数解可能在迭代时就已求出，所以在迭代时需要进行特判。
每一次有效的操作至少会将 (p) 除以 (2) ，求解 (gcd) 的复杂度为 (O(log_2n)),故这样迭代的总复杂度为 (O(log_2^2n))
然后就可以求解了！
贴代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll ksm(ll a,ll b,ll p){
ll ans=1;
for(;b;b>>=1,a=1ll*a*a%p)
if(b&1) ans=1ll*ans*a%p;
return ans;
}
ll gcd(ll a,ll b){
if(!b) return a;
return gcd(b,a%b);
}
ll bsgs(ll a,ll b,ll p){
unordered_map<int,int> mp;
ll tim=0,A=1;
while(1){
ll t=gcd(a,p);if(t==1) break;
if(b%t) return -1;
b/=t,p/=t,A=1ll*A*(a/t)%p;
++tim;
if(b==A) {
return tim;
}
}
ll m=sqrt(p)+1;
ll tmp=b;
for(ll i=0;i<m;++i,tmp=1ll*tmp*a%p) mp[tmp]=i;
tmp=ksm(a,m,p);
ll now=1ll*A*tmp%p;
for(ll i=1;i<=m;++i,now=1ll*now*tmp%p){
if(mp[now]){
if(i*m-mp[now]+tim>=0) return i*m-mp[now]+tim;
}
}
return -1;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
ll x,y,z;
while(cin>>x>>y>>z&&(x||y||z)){
ll tmp=bsgs(x,z,y);
if(tmp==-1) cout<<"No Solution"<<'
';
else cout<<tmp<<'
';
}
return 0;
}