BZOJ-1467/2480: Spoj3105 Mod

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);
    }
}