POJ 3243 Clever Y | BSGS算法完全版

题目:

给你A,B,K

求最小的x满足A^x=B (mod K)

题解:

如果A,C互质请参考上一篇博客

将 A^x≡B(mod C) 看作是A^x+Cy=B方便叙述与处理.

我们将方程一直除去A,C的最大公约数进行变形,最终使得A和C互质.

将方程同除d₁=gcd(A,C),得到B₁=A/d₁*A^x-1+C₁y.有可能A和C₁不互素,因此继续将方程同除d₂=gcd(A,C₁)得到B₂=A²/d₁d₂*A^i-2+C₂y.一直这样下去知道A和C_i互素.这里也能看出,若B_i不被gcd(A,C_i)整除则无解.

最终得到B_n=Aⁿ/d₁d₂...d_n*A^x-n+C_ny,并记D=Aⁿ/d₁d₂...d_n,易证明gcd(D,C_n)=1,因此存在D的逆元,可以将最后的式子变为A ^x-n≡B_nD^-1(mod C_n),此时就能求解了.

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cmath>
  5 typedef long long ll;
  6 using namespace std;
  7 ll x,z,k;
  8 ll Gcd(ll x,ll y)
  9 {
 10     return y==0?x:Gcd(y,x%y);
 11 }
 12 ll exGcd(ll a,ll b,ll &x,ll &y)
 13 {
 14     if (b==0) return x=1,y=0,a;
 15     ll r=exGcd(b,a%b,y,x);
 16     y-=a/b*x;
 17     return r;
 18 }
 19 ll inv(ll a,ll m)
 20 {
 21     ll x,y;
 22     exGcd(a,m,x,y);
 23     return (x%m+m)%m;
 24 }
 25 namespace Hash
 26 {
 27     const ll N=50000;
 28     const ll H=999979;
 29     struct adj
 30     {
 31     ll nxt,v,num,val;
 32     }e[N];
 33     ll  head[H],ecnt=0;
 34     void init()
 35     {
 36     ecnt=0;
 37     memset(head,0,sizeof(head));
 38     }
 39     void insert(ll x,ll val)
 40     {
 41     ll org=x;
 42     x%=H;
 43     for (int i=head[x];i;i=e[i].nxt)
 44     {
 45         if (e[i].num==org)
 46         {
 47         e[i].val=val;
 48         return ;
 49         }
 50     }
 51     e[++ecnt].num=org;
 52     e[ecnt].val=val;
 53     e[ecnt].nxt=head[x];
 54     head[x]=ecnt;
 55     }
 56     ll query(ll x)
 57     {
 58     ll org=x;
 59     x%=H;
 60     for (int i=head[x];i;i=e[i].nxt)
 61         if (e[i].num==org) return e[i].val;
 62     return -1;
 63     }
 64 }
 65 ll BSGS(ll a,ll b,ll c)
 66 {
 67     ll cnt=0,G,d=1;
 68     while ((G=Gcd(a,c))!=1)
 69     {
 70     if (b%G!=0) return -1;
 71     cnt++,b/=G,c/=G;
 72     d=d*(a/G)%c;
 73     }
 74     b=b*inv(d,c)%c;
 75     Hash::init();
 76     ll s=sqrt(c*1.0);
 77     ll p=1;
 78     for (int i=0;i<s;i++)
 79     {
 80     if (p==b) return i+cnt;
 81     Hash::insert(p*b%c,i);
 82     p=p*a%c;
 83     }
 84     ll q=p,t;
 85     for (int i=s;i-s+1<=c-1;i+=s)
 86     {
 87     t=Hash::query(q);
 88     if (t!=-1) return i-t+cnt;
 89     q=q*p%c;
 90     }
 91     return -1;
 92 }
 93 int check()
 94 {
 95     for (ll i=0,j=1;i<=10;i++)
 96     {
 97     if (j==k)
 98     {
 99         printf("%lld
",i);
100         return 1;
101     }
102     j=j*x%z;
103     }
104     if (x==0)
105     {
106     puts("No Solution");
107     return 1;
108     }
109     return 0;
110 }
111 int main()
112 {
113     while (scanf("%lld%lld%lld",&x,&z,&k) && x+z+k>0)
114     {
115     x%=z,k%=z;
116     if (check()) continue;
117     ll ans=BSGS(x,k,z);
118     if (ans==-1) puts("No Solution");
119     else printf("%lld
",ans);
120     }
121     return 0;
122 }