本文共 1524 字，大约阅读时间需要 5 分钟。
#include #include #include using namespace std;typedef long long ll;int a, b, p;ll x, y, z;ll exgcd(ll a, ll b, ll &x, ll &y){ if(!b){ x = 1; y = 0; return a; } ll d = exgcd(b, a % b, x, y); ll z = x; x = y; y = z - a / b * y; return d;}int fast_pow(int n, int k){ //n^k%p int ans = 1; while(k){ if(k & 1) ans = (ll)ans * n % p; n = (ll)n * n % p; k >>= 1; } return ans;}ll BSGS(){ //a^x≡b(mod p) map hash; hash.clear(); int t = ceil(sqrt(p)), val = b, j = 1; for(int i = 0; i < t; ++i){ hash[val] = i; val = (ll)val * a % p; } a = fast_pow(a, t); if(!a) return !b ? 1 : -1; for(int i = 0; i <= t; ++i){ int k = hash.find(j) == hash.end() ? -1 : hash[j]; if(k >= 0 && (i * t - k) >= 0) return (ll)i * t - k; j = (ll)j * a % p; } return -1;}int T, K;int main(){ scanf("%d%d", &T, &K); if(K == 3) while(T--){ scanf("%d%d%d", &a, &b, &p); int ans = BSGS(); ans == -1 ? puts("Orz, I cannot find x!") : printf("%d\n", ans); } else if(K == 1) while(T--){ scanf("%d%d%d", &a, &b, &p); printf("%d\n", fast_pow(a, b)); } else while(T--){ scanf("%d%d%d", &a, &b, &p); if(b % (z = exgcd(a, p, x, y))) puts("Orz, I cannot find x!"); else printf("%d\n", ((ll)x * b / z % p + p) % p); } return 0;}
转载于:https://www.cnblogs.com/Qihoo360/p/9741524.html