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
| #include <cstdio> #include <cmath> #include <unordered_map> using namespace std; typedef long long LL; const int inf = 1e8; int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1, y = 0; return a; } int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } int bsgs(int a, int b, int p) { if (1 % p == b % p) return 0; int k = sqrt(p) + 1; unordered_map<int, int> hash; for (int i = 0, j = b % p; i < k; i++) { hash[j] = i; j = (LL)j * a % p; } int t = 1; for (int i = 0; i < k; i++) t = (LL)t * a % p; for (int i = 1, j = t; i <= k; i++) { if (hash.count(j)) return i * k - hash[j]; j = (LL)j * t % p; } return -inf; } int exbsgs(int a, int b, int p) { b = (b % p + p) % p; if (1 % p == b % p) return 0; int x, y; int d = exgcd(a, p, x, y); if (d > 1) { if (b % d) return -inf; exgcd(a / d, p / d, x, y); return exbsgs(a, (LL)b / d * x % (p / d), p / d) + 1; } return bsgs(a, b, p); } int main() { int a, p, b; while (~scanf("%d%d%d", &a, &p, &b) && a && p && b) { int res = exbsgs(a, b, p); if (res < 0) puts("No Solution"); else printf("%d\n", res); } return 0; }
|