\[a^b = c\;(mod\;p)
\]
\[a^0,a^1,a^2,\cdots,a^{\sqrt{p}-1}
\]
\[a^{\sqrt{p}},a^{\sqrt{p}+1},\cdots,a^{2\sqrt{p}-1}
\]
\[\cdots
\]
\[a^{^{(\sqrt{p}-1)×\sqrt{p}}},\cdots,a^{p-1}
\]
\[a^k=c\;(mod\;p)
\]
\[a^r=\frac{c}{a^{(i-1)×\sqrt{p}}}
\]
\[∵a^{p-1}\equiv1(mod\;p)
\]
\[∴a^{p-2}×a\equiv1(mod\;p)
\]
\[O(\sqrt{p}×log\;p)\;\;=> AC
\]
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
#define int long long
int a,d,p,s[233333],sq;
map<int,int> mp;
int ksm(int a,int b,int mod)//快速幂
{
int ans=1;
while(b)
{
if(b&1)ans=1LL*ans*a%mod;
a=1LL*a*a%mod;
b>>=1;
}
return ans;
}
int BSGS()
{
sq=ceil(sqrt(p));
s[0]=1;mp[1]=0;
for(int i=1;i<=sq;i++)
{
s[i]=1LL*s[i-1]*a%p;
mp[s[i]]=i;
//用哈希表记录
if(s[i]==d)return i;
//若在第一行发现答案,直接输出
}
int dif=ksm(a,sq,p);
for(int l=sq+1,r=sq+sq,i=2;l<p;l+=sq,r+=sq,i++)
{
int inv=ksm(dif,i-1,p);
inv=ksm(inv,p-2,p);//求逆元
int t=1LL*d*inv%p;
if(mp.count(t))return mp[t]+(i-1)*sq;
//如果在第1行中查询存在,则说明第i行有答案
}
return -1;//说明无解
}
signed main()
{
scanf("%lld%lld%lld",&p,&a,&d);
if(d>=p||a>=p)//特殊情况
{
puts("no solution");
return 0;
}
int res=BSGS();
if(res==-1)puts("no solution");
else printf("%lld\n",res);
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章