exBSGS 板子,但是该数据下出错了 input:
46 40 36
10 48 4
0 0 0
answer:
2
2
output:
No Solution
No Solution
感觉是 exBSGS 函数里的判断有问题
// Code by iamsh
#include<bits/stdc++.h>
using namespace std;
long long BSGS(long long a,long long b,long long p) {
// cout << a << " " << b << " " << p << "\n";
if(p == 1) {
return 0;
}
long long A = sqrtl(p) + 1,c = 1;
unordered_map<long long,long long> mp;
for(long long n = 0;n <= A;n ++) {
mp[b % p] = n,b = b * a % p;
if(n) {
c = c * a % p;
}
}
b = c;
for(long long m = 1;m <= A;m ++) {
if(mp.count(b)) {
return m * A - mp[b];
}
b = b * c % p;
}
return -1;
}
long long exgcd(long long a,long long b,long long &x,long long &y) {
if(!b) {
x = 1,y = 0;
return a;
}
long long ans = exgcd(b,a % b,y,x);
y -= a / b * x;
return ans;
}
long long exBSGS(long long a,long long b,long long p) {
if(p == 1 || b % p == 1) {
return 0;
}
if(a % p == b % p) {
return 1;
}
long long x,y,s = 1,k = 0;
long long g = exgcd(a,p,x,y);
while(g > 1) {
// cout << a << " " << b << " " << p << "\n";
// cout << b << " " << g << "\n";
if(b % g) {
return -1;
}
k ++,b /= g,p /= g;
s = a / g * s % p;
g = exgcd(a,p,x,y);
}
exgcd(s,p,x,y);
b = b * (x % p + p) % p;
long long res = BSGS(a,b,p);
return res < 0 ? res : res + k;
}
void solve() {
long long p,a,b;
cin >> a >> p >> b;
if(!p && !a && !b) {
exit(0);
}
long long res = exBSGS(a,b,p);
if(res < 0) {
cout << "No Solution\n";
}
else {
cout << res << "\n";
}
}
int main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cout << fixed << setprecision(12);
int t = 1e9;
// cin >> t;
while(t --) {
solve();
}
return 0;
}