求 (A^xequiv B(mod p))
为什么不能有BSGS了？ 因为 我们的BSGS是根据欧拉定理的出来的。
欧拉定理 当 a p互质的时候 (a^{phi(p)}equiv 1mod p)
所以 我们在BSGS的时候 质数始终都是在[0,(phi(p))-1]之中的。
这也是我们对于 一个质数m 采用根号 求一半的原因所在。
但是 当a p不互质的时候 我么有 扩展欧拉定理 (a^cequiv a^{cmod phi(p)+phi(p)}mod p)
当然 这个东西起不到什么大的作用。
所以 这个时候需要 扩展欧拉定理的上场。
一个结论：当(a,p)不整除b且(b eq 1)时 方程无自然数解。
这是因为 对于同余式 (a^xequiv b(mod p))而言 (a,p)>1 此时将式子展开为 (acdot a^{x-1}+kcdot p=b)的形式 可以发现等式右边都有共有的因数(a,p);
然后 同除以(a,p) 右边为小数 而左边一定为整数 故方程无解。
当然上述式子是在x>0时 成立 考虑当x0时 必然有b1。
所以对于 (a,p)>1 且 (a,p)|b 设 g=(a,p);
那么原式为 (a^{x-1}cdot frac{a}{g}equiv frac{b}{g}(mod frac{p}{g}))
这个等式 显然是成立的。
可以发现我们得到了一个新的等式 如果此时新的 a 和 p互质了我们显然可以直接BSGS了。
如果不行 递归的进行这个操作。显然每次除以的Gcd不为1 所以最多log次。
值得注意的是 递归的时候 我们发现了
((a^{x-1},frac{p}{g}))不整除(frac{frac{b}{g}}{frac{a}{g}}) 此时也是无解的。
但是注意 由于p不是质数 所以我们需要 exgcd来求逆元。
(还挺麻烦这个算法 但是这个再麻烦也没大组合数取模版本ex...
const ll MAXN=100010;
ll a,p,b,x,y;
map<ll,ll>H;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline void exgcd(ll a,ll b)
{
if(!b){x=1,y=0;return;}
exgcd(b,a%b);
ll z=x;x=y;y=z-a/b*y;
}
inline ll inv(ll a,ll p)//a的逆元
{
exgcd(a,p);
return (x%p+p)%p;
}
inline ll ksm(ll b,ll p,ll mod)
{
ll cnt=1;
while(p)
{
if(p&1)cnt=cnt*b%mod;
b=b*b%mod;p=p>>1;
}
return cnt;
}
inline ll BSGS(ll a,ll b,ll p)
{
H.clear();
ll m=(ll)sqrt(p*1.0)+1;
ll w1=1;H[b]=0;
rep(1,m,i)
{
w1=w1*a%p;
ll cc=w1*b%p;
H[cc]=max(H[cc],i);
}
ll cc=1;
rep(1,m,i)
{
cc=cc*w1%p;
if(H.find(cc)!=H.end())
return i*m-H[cc];
}
return -1;
}
inline ll exBSGS()
{
a%=p;b%=p;
if(b==1)return 1;
ll k=0;
ll wp=p,w1=1,g;
while((g=gcd(a,wp))>1)
{
if(b%g)return -1;
++k;w1=a/g;b=b/g;wp=wp/g;
b=b*inv(w1,wp)%p;
if(b==1)return k;
}
ll ans=BSGS(a,b,wp);
return ans<0?ans:ans+k;
}
signed main()
{
freopen("1.in","r",stdin);
while(1)
{
get(a);get(p);get(b);
//求 a^x=b(mod p)
if(!a&&!p&&!b)return 0;
ll ans=exBSGS();
if(ans<0)puts("No Solution");
else putl(ans);
}
return 0;
}
这个东西常数有点大了 外面一个T组数据 T<=100 里面是log+sqrt(p)log的 估计map常数大 所以开o2才过。
想的话可以手写hash 不过每次还要情况链表什么的。