「SPOJ 3105」Power Modulo Inverted

传送门

题目大意：

求关于 \(x\) 的方程
\[ a^x \equiv b \;(\mathrm{mod}\; p) \]
的最小自然数解，不保证 \(a,p\) 互质

---

如果保证 \(a,p\) 互质，那么可以直接使用 \(\texttt{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"<<'\n';
        else cout<<tmp<<'\n'; 
    }   
    return 0;
}