結果
問題 | No.1140 EXPotentiaLLL! |
ユーザー | chocopuu |
提出日時 | 2020-07-31 22:10:42 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,933 bytes |
コンパイル時間 | 2,188 ms |
コンパイル使用メモリ | 208,008 KB |
実行使用メモリ | 50,688 KB |
最終ジャッジ日時 | 2024-07-06 18:25:37 |
合計ジャッジ時間 | 6,372 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | AC | 58 ms
50,560 KB |
testcase_09 | AC | 58 ms
50,688 KB |
testcase_10 | AC | 55 ms
50,636 KB |
testcase_11 | AC | 58 ms
50,560 KB |
testcase_12 | AC | 56 ms
50,688 KB |
ソースコード
#include "bits/stdc++.h" using namespace std; #define int long long #define REP(i, n) for (int i = 0; i < (int)n; ++i) #define RREP(i, n) for (int i = (int)n - 1; i >= 0; --i) #define FOR(i, s, n) for (int i = s; i < (int)n; ++i) #define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i) #define ALL(a) a.begin(), a.end() #define IN(a, x, b) (a <= x && x < b) template<class T>inline void out(T t){cout << t << "\n";} template<class T,class... Ts>inline void out(T t,Ts... ts){cout << t << " ";out(ts...);} template<class T>inline bool CHMIN(T&a,T b){if(a > b){a = b;return true;}return false;} template<class T>inline bool CHMAX(T&a,T b){if(a < b){a = b;return true;}return false;} constexpr int INF = 1e18; #define endl '\n' #define IOS() ios_base::sync_with_stdio(0);cin.tie(0) // a^b long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } // a^-1 long long modinv(long long a, long long m) { long long b = m, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } // a^x ≡ b (mod. m) となる最小の正の整数 x を求める long long modlog(long long a, long long b, int m) { a %= m, b %= m; // calc sqrt{M} long long lo = -1, hi = m; while (hi - lo > 1) { long long mid = (lo + hi) / 2; if (mid * mid >= m) hi = mid; else lo = mid; } long long sqrtM = hi; // {a^0, a^1, a^2, ..., a^sqrt(m)} map<long long, long long> apow; long long amari = 1; for (long long r = 0; r < sqrtM; ++r) { if (!apow.count(amari)) apow[amari] = r; (amari *= a) %= m; } // check each A^p long long A = modpow(modinv(a, m), sqrtM, m); amari = b; for (long long q = 0; q < sqrtM; ++q) { if (apow.count(amari)) { long long res = q * sqrtM + apow[amari]; if (res > 0) return res; } (amari *= A) %= m; } // no solutions return -1; } const int M = 2750131; int P[200000]; int invP[M + 1]; int minP[M + 1]; bool isP[M + 1]; void Eratosthenes() { int p = 0; REP(i, M + 1) isP[i] = true, minP[i] = -1; isP[0] = isP[1] = false; minP[0] = 0; minP[1] = 1; FOR(i, 2, M + 1) { if (isP[i]) { minP[i] = i; P[p] = i; invP[i] = p++; for (int j = i * 2; j < M; j += i) { isP[j] = false; if (minP[j] == -1) minP[j] = i; } } } } void solve(){ int A, P; cin >> A >> P; if(!isP[P]) { out(-1); return; } out(modpow(A % P, (P - 1) * P, P)); } signed main(){ IOS(); Eratosthenes(); int Q = 1; cin >> Q; while(Q--)solve(); }