YM zky跑得飞快的BSGS
数论模板题,复习下数论
过不了样例都能A是闹哪样啊233
Code:
#include <cstdio> #include <map> #include <cmath> using namespace std; map<long long, long long> s; long long y, z, p, T, k; inline long long exgcd(long long a, long long b, long long &x, long long &y) { if(!b) { x = 1, y = 0; return a; } else { long long d = exgcd(b, a % b, x, y), t = x; x = y, y = t - a / b * y; return d; } } inline long long quick_pow(long long n, long long m, long long p) { long long res = 1; while (m) { if (m & 1) res = res * n % p; m >>= 1; n = n * n % p; } return res; } inline void INV(long long a, long long b, long long p) { a = quick_pow(a, p-2, p); b = b * a % p; if (!b) puts("Orz, I cannot find x!"); else printf("%lld\n", b); } inline long long gcd(long long a, long long b) { long long t; while(b) { t = a % b; a = b; b = t; } return a; } inline long long inv(long long a) { if (gcd(a, p) == 1) return quick_pow(a, p-2, p); long long d, x, y; d = exgcd(a, p, x, y); return d == 1 ? (x + p) % p : -1; } inline void BSGS(long long a, long long b, long long p) { int i; long long m = sqrt(p) + .5, v = inv(quick_pow(a,m,p)), e = 1; s.clear(); s[1] = 0; for(i = 1;i < m; ++i) e = e * a % p, s[e] = i; for(i = 0;i <= m; ++i) { if(s.count(b)) { printf("%lld\n", i * m + s[b]); return; } b = b * v % p; } puts("Orz, I cannot find x!"); } inline void solve(long long type) { switch (type) { case (1) :{ printf("%d\n", quick_pow(y, z, p)); break; } case (2) :{ INV(y, z, p); break; } case (3) :{ BSGS(y, z, p); break; } } } char c; inline void read(long long &x) { for (c = getchar();c > '9' || c < '0';c = getchar()); for (x = 0;c >= '0' && c <= '9';c = getchar()) x = (x << 3) + (x << 1) + c - '0'; } int main() { read(T), read(k); while (T--) { read(y), read(z), read(p); solve(k); } }