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
|
using namespace std; inline int (int a, int b, int mod, int k = 1) { int q = sqrt(mod) + 1; unordered_map<int, int> mp; int now = 1, tmp; for(int i = 0; i < q; i++, now = 1ll * now * a % mod) { mp[1ll * now * b % mod] = i; } tmp = now; for(int i = 1; i <= q; i++, now = 1ll * now * tmp % mod) if(mp.count(1ll * k * now % mod) != 0) return i * q - mp[1ll * k * now % mod]; return -1; } inline int gcd(int a, int b) {return a == 0 || b == 0 ? a | b : gcd(b, a % b);} inline int exBSGS(int a, int b, int mod, int k = 1) { if(b == k) return 0; if(a == 0 && b == 0) return 1; if(a == 0) return -1; if(b == 0) { int now = k, ans = 0; int g = gcd(k, mod); for(int tmp = mod / g; tmp != 1; tmp /= g) { g = gcd(tmp, a); if(g == 1) return -1; } while(now) now = 1ll * now * a % mod, ans++; return ans; } int g = gcd(a, mod); if(b % g) return -1; if(g == 1) return BSGS(a, b, mod, k); int ans = exBSGS(a % (mod / g), b / g, mod / g, 1ll * k * (a / g) % (mod / g)); return ~ans ? ans + 1 : ans; } int main() { int a, b, mod; while(1) { scanf("%d%d%d", &a, &mod, &b); if(a + b + mod == 0) return 0; int ans = exBSGS(a % mod, b % mod, mod); ~ans ? printf("%dn", ans) : puts("No Solution"); } return 0; }
|
近期评论