为什么会RE啊QAQ
本机测试可以的啊qwq
#include<bits/stdc++.h>
using namespace std;
int mod;
int qpow(int x, int y) {
if(x == 0) return 0;
int res = 1;
while(y) {
if(y & 1) res = 1ll * res * x % mod;
x = 1ll * x * x % mod, y >>= 1;
}
return res;
}
int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x % y);
}
void exgcd(int a, int b, int &x, int &y) {
if(b == 0) {
x = 1, y = 0;
return;
}
exgcd(b, a % b, y, x), y -= (a / b) * x;
}
int ny(int a) {
int x, y;
exgcd(a, mod, x, y), x = (x % mod + mod) % mod;
}
void BSGS(int a, int b) {
unordered_map<int, int> qwq;
int t, tmp = 0, kuai;
a %= mod, b %= mod;
if(b == 1 || mod == 1) return (void)(printf("0\n"));
while((t = gcd(a, mod)) != 1) {
if(b % t) return (void)(printf("No Solution\n"));
b /= t, mod /= t, b = 1ll * b * ny(a / t) % mod;
++tmp;
if(b == 1) return (void)(printf("%d\n", tmp));
}
kuai = sqrt(mod);
for(int i = 0, now = 1; i < kuai; i++, now = 1ll * now * a % mod)
qwq[1ll * b * now % mod] = i;
for(int i = 1, ch = qpow(a, kuai), now = ch; i <= kuai; i++, now = 1ll * now * ch % mod)
if(qwq[now]) return (void)(printf("%d\n", i * kuai - qwq[now] + tmp));
return (void)(printf("No Solution\n"));
}
int a, b;
int main() {
int t = clock();
while(1) {
scanf("%d%d%d",&a,&mod,&b);
if(mod + a + b == 0) break;
BSGS(a, b);
}
return 0;
}