扩展篇
问题：
当
p
，
a
p，a
p，a可能不互质时，求
a
x
≡
b
(
m
o
d
p
)
a^x\equiv b(mod~p)\\
ax≡b(mod p)
方法:
当
d
1
=
g
c
d
(
a
,
p
)
≠
1
d_1=gcd(a,p)\neq1
d1=gcd(a,p)=1，当
d
1
∤
b
d_1\nmid b
d1∤b时，无解，则原式变成：
a
d
1
a
x
−
1
≡
b
d
1
(
m
o
d
p
d
1
)
\frac a{d_1}a^{x-1}\equiv \frac b{d_1}(mod~\frac p{d_1})\\
d1aax−1≡d1b(mod d1p)
当设
d
2
=
g
c
d
(
a
,
p
d
1
)
≠
1
d_2=gcd(a,\frac p{d_1})\neq1
d2=gcd(a,d1p)=1，当
d
2
∤
b
d
1
d_2\nmid \frac b{d_1}
d2∤d1b时，无解，则原式可变成：
a
2
d
1
d
2
a
x
−
2
≡
b
d
1
d
2
(
m
o
d
p
d
1
d
2
)
\frac {a^2}{d_1d_2}a^{x-2}\equiv \frac b{d_1d_2}(mod~\frac p{d_1d_2})\\
d1d2a2ax−2≡d1d2b(mod d1d2p)
重复直到
d
c
n
t
=
1
d_{cnt}=1
dcnt=1。设
D
=
∏
i
=
1
c
n
t
d
i
D=\prod_{i=1}^{cnt}d_i
D=∏i=1cntdi，原式可以写成：
a
c
n
t
D
a
x
−
c
n
t
≡
b
D
(
m
o
d
p
D
)
\frac {a^{cnt}}Da^{x-cnt}\equiv \frac bD(mod~\frac pD)\\
Dacntax−cnt≡Db(mod Dp)
剩下的
a
x
−
c
n
t
,
b
D
,
p
D
a^{x-cnt},\frac bD,\frac pD
ax−cnt,Db,Dp，可以构成基础篇的
b
s
g
s
bsgs
bsgs，修改的地方就是乘了一个系数
a
c
n
t
D
\frac {a^{cnt}}D
Dacnt。
注意： c n t cnt cnt可能大于x这个解，所以我们在做除法的时候就要判断是不是能够相等，相等直接输出当前的 c n t cnt cnt。
题目：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll qpow(ll x, ll y, ll mod) {
ll ans = 1;
while(y) {
if(y & 1) ans = ans * x % mod;
x = x * x % mod;
y >>= 1;
}
return ans;
}
unordered_map<ll, ll> mp;
ll bsgs(ll a, ll b, ll p, ll ad) {
if(a % p == 0 && b%p != 0) return -1;
mp.clear();
int k = ceil(sqrt(p));
for(int i=0; i<k; i++) {
mp[b] = i;
b = b * a % p;
}
ll aa = qpow(a, k, p), A = aa*ad % p;
for(int i=1; i<=k; i++) {
if(mp[A]) return 1ll*i*k - mp[A];
A = A * aa % p;
}
return -1;
}
ll exgcd(ll &x, ll &y, ll a, ll b) {
if(b == 0) {
x = 1, y = 0;
return a;
}
ll d = exgcd(x, y, b, a%b);
ll tmp = y;
y = x - a/b * y;
x = tmp;
return d;
}
ll inv(ll a, ll b) {
ll x, y;
ll d = exgcd(x, y, a, b);
return x;
}
ll exbsgs(ll a, ll b, ll p) {
a %= p, b %= p;
if(b == 1 || p == 1) return 0;
ll cnt = 0, d, tmp = 1;
while((d = __gcd(a, p)) ^ 1) {
if(b % d) return -1;
cnt++, b /= d, p /= d;
tmp = tmp * a/d % p;
if(tmp == b) return cnt;
}
ll ans = bsgs(a, b, p, tmp);
if(ans == -1) return -1;
else return ans + cnt;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ll a, p, b, d;
while(cin >> a >> p >> b) {
if(!a || !p || !b) break;
ll ans = exbsgs(a, b, p);
if(ans != -1) cout << ans << endl;
else cout << "No Solution\n";
}
return 0;
}