题目描述
已知数a,p,b，求满足a^x≡b(mod p)的最小自然数x。
输入
每个测试文件中最多包含100组测试数据。
每组数据中，每行包含3个正整数a,p,b。
当a=p=b=0时，表示测试数据读入完全。
输出
对于每组数据，输出一行。
如果无解，输出“No Solution”（不含引号），否则输出最小自然数解。
样例输入
5 58 33
2 4 3
0 0 0
2 4 3
0 0 0
样例输出
9
No Solution
No Solution
提示
100%的数据，a,p,b≤1e9。
$EXBSGS$模板题，注意特判当$p=1$时输出$0$。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
map<int,int>mp;
ll a,b,p,ans;
inline ll gcd(ll x,ll y)
{
return y==0?x:gcd(y,x%y);
}
inline void exgcd(ll &x,ll &y,ll a,ll b)
{
if(!b)
{
x=1,y=0;
return ;
}
exgcd(y,x,b,a%b);
y-=(a/b)*x;
return ;
}
inline ll quick(ll x,ll y,ll mod)
{
ll res=1ll;
while(y)
{
if(y&1)
{
res=res*x%mod;
}
y>>=1;
x=x*x%mod;
}
return res;
}
inline ll BSGS(ll a,ll b,ll p,ll g)
{
ll x,y;
ll m=ceil(sqrt(p));
exgcd(x,y,g,p);
b=(b*x%p+p)%p;
ll num=quick(a,m,p);
exgcd(x,y,num,p);
num=(x%p+p)%p;
ll sum=1ll;
mp.clear();
for(int i=0;i<=m;i++)
{
if(!mp.count(sum))
{
mp[sum]=i;
}
sum*=a,sum%=p;
}
for(int i=0;i<=m;i++)
{
if(mp[b])
{
return mp[b]+i*m;
}
b*=num,b%=p;
}
return -1;
}
inline int EX_BSGS(int a,int b,int p)
{
ll g=1ll;
ll k=0;
ll d,ans;
if(b==1)
{
return 0;
}
while((d=gcd(a,p))!=1)
{
if(b%d)
{
return -1;
}
k++,b/=d,p/=d,g=g*(a/d)%p;
if(g==b)
{
return k;
}
}
ans=BSGS(a,b,p,g);
return ans==-1?-1:ans+k;
}
int main()
{
while(scanf("%d%d%d",&a,&p,&b))
{
if(!a&&!b&&!p)
{
break;
}
if(p==1)
{
printf("0\n");
continue;
}
ans=EX_BSGS(a,b,p);
printf(ans==-1?"No Solution\n":"%d\n",ans);
}
}