[文章目录]
Description
已知数a,p,b，求满足a^x≡b(mod p)的最小自然数x。a,p,b≤1e9
扩展BSGS
由于a，p可能不互质，所以原来的BSGS方法不适用。
那么我们可以这样，令d=gcd(a,p)。原方程等价于：a/d * a^(x-1)=b/d (mod p/d) 如果b不是d的约数，那么无解。发现有可能a和p/d依然不互质，我们循环进行这一过程，直到互质为止。之后直接套用BSGS解法即可。假设除gcd除了k次，那么最后的答案即为x+k。
发现当答案x=0~k-1的时候，这个方法没有处理，所以在开始的时候枚举检验答案到logc【k<=logc】。
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int a,b,p;
map<int,int>mp;
int gcd(int x,int y){return !y ? x : gcd(y,x%y);}
int main()
{
while(~scanf("%d%d%d",&a,&p,&b))
{
if(a==0&&p==0&&b==0) return 0;
mp.clear(); b%=p; a%=p;
if(a==0)
{
if(b!=0) puts("No Solution");
else puts("0");
continue;
}
ll now=1%p; int ans=-1;
for(int i=0;i<=30;++i)
{
if(now==b) {ans=i; break;}
now=now*a%p;
}
if(ans!=-1){printf("%d\n",ans); continue;}
now=1; int d=gcd(a,p),cnt=0;
while(d!=1)
{
if(b%d!=0) {puts("No Solution"); ans=0; break;}
p/=d; now=now*a/d%p; cnt++; b/=d;
d=gcd(a,p);
}
if(ans!=-1) continue;
int m=(int)sqrt(p)+10;
ll po=1;
for(int i=0;i<m;++i) {mp[po*b%p]=i; po=po*a%p;}
for(int i=1;i<=m+1;++i)
{
now=now*po%p;
if(mp.find(now)!=mp.end())
{
ans=i*m-mp[now];
break;
}
}
if(ans==-1) puts("No Solution");
else printf("%d\n",ans+cnt);
}
}