P4195

发表于 分类于
【模板】扩展 BSGS/exBSGS

【模板】扩展 BSGS/exBSGS

求解：

$$ a ^ x \equiv b \pmod { p }$$

其中 $a,p$ 不一定互质（即 $a$ 不一定有逆元）。

想办法让其互质，使我们可以正常地使用 BSGS 算法。

具体地，先使 $d _ 1 = \gcd ( a , p )$。如果 $d _ 1 \nmid b$，则原方程无大于 $1$ 的解；反之，我们可以把方程同时除以 $d _ 1 $，得到：

$$ \dfrac { a } { d _ 1 } a ^ { x - 1 } \equiv \dfrac { b } { d _ 1 } \pmod { \dfrac{ p }{ d _ 1 } } $$

如果 $a$ 与 $ p / d _ 1 $ 仍然不互质，就重复上面的步骤。

令 $d _ 2 = \gcd ( a , p / d _ 1 )$。如果 $d _ 2 \nmid ( b / d _ 1 )$，则原方程无大于当前 $k$ 的解；反之，我们可以把方程再同时除以 $ d _ 2 $，得到：

$$ \dfrac { a ^ 2 } { d _ 1 d _ 2 } a ^ { x - 2 } \equiv \dfrac { b } { d _ 1 d _ 2 } \pmod { \dfrac { p }{ d _ 1 d _ 2 }}$$

依次类推，令 $D = \prod _ { i = 1 } ^ { k } d _ i$ 最后使得 $a \perp ( p / D )$。

此时我们的方程为：

$$ \dfrac { a ^ k } { D } a ^ { x - k } \equiv \dfrac { b } { D } \pmod { \dfrac { p } { D } }$$

好了，现在 $ a ^ k / D $ 是有逆元的，直接除过去就化成了最基本的能使用 BSGS 的形式，用就完了。

至于最后的解 $ x $ 有可能小于等于 $ k $，而上面的方法只能把 $ x > k $ 的解给解出来。

所以直接 $ O ( k ) $ 枚举一下这个东西就好了。

时间复杂度 $ O(\log p + \sqrt{ p }) $。

以下代码在开 -O2 的状态下，评测机稳定时能够通过。。。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}

const ll N=1e6;

ll a,p,b,pp,bb,tot,k,sp,ans,flg;
ll val[N+5],nxt[N+5];
map<ll,ll> head;

inline ll Exgcd(ll a,ll b,ll &x,ll &y) {
  if(b==0) {x=1;y=0;return a;}ll r=Exgcd(b,a%b,y,x);y-=a/b*x;return r;
}

inline ll Pow(ll b,ll p,ll mo) {
  ll r=1;while(p) {if(p&1) r=r*b%mo;b=b*b%mo;p>>=1;}return r;
}

inline void Addhash(ll x,ll v) {
  val[++tot]=v;
  if(head.find(x)!=head.end()) nxt[tot]=head[x];
  head[x]=tot;
}

inline void Findhash(ll x,ll v) {
  if(head.find(x)!=head.end()) {
    for(ll i=head[x];i;i=nxt[i]) {
      ll tmp=v*sp-val[i];
      if(tmp>=0) {
        if(ans<0||tmp<ans) ans=tmp;
      }
    }
  }
}

inline ll BSGS(ll a,ll b,ll p) {
  for(ll i=1;i<=tot;i++) nxt[i]=val[i]=0;
  tot=0;head.clear();
  sp=ceil(sqrt(p));
  ll r=b%p;for(ll i=0;i<=sp;i++) {Addhash(r,i);r=r*a%p;}
  ll sr=Pow(a,sp,p);r=1;ans=-k-1;
  for(ll i=0;i<=sp;i++) {Findhash(r,i);r=r*sr%p;}
  return ans;
}

inline void Init() {
  ll d=1,tmpp=1;k=0;ll x0=0,y0=0;
  while(Exgcd(a,p/d,x0,y0)!=1) {
    k++;
    ll tmpd=Exgcd(a,p/d,x0,y0);
    d=d*tmpd;
    if(b%d!=0) {flg=0;break;}
  }
  pp=p/d;
  if(flg) {
    tmpp=Pow(a,k,pp);
    Exgcd(tmpp,pp,x0,y0);
    x0=(x0%pp+pp)%pp;bb=b*x0%pp;
  }
}

int main() {

  while(1) {
    a=read();p=read();b=read();
    if(a==0&&p==0&&b==0) break;flg=1;b%=p;
    if(b==1||p==1) {writeln(0);continue;}
    Init();
    if(!flg) {
      ll x=-1,r=1;
      for(ll i=0;i<=k;i++) {
        if(r==b) {x=i;break;}r=r*a%p;
      }
      if(x>=0) writeln(x);
      else printf("No Solution\n");
    }
    else {
      ll x=BSGS(a,bb,pp)+k;
      ll r=1;
      for(ll i=0;i<=k;i++) {
        if(r==b) {x=i;break;}r=r*a%p;
      }
      if(x<0) {printf("No Solution\n");}
      else writeln(x);
    }
  }

  return 0;
}