結果
問題 | No.1140 EXPotentiaLLL! |
ユーザー |
![]() |
提出日時 | 2020-07-31 22:05:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,701 bytes |
コンパイル時間 | 2,963 ms |
コンパイル使用メモリ | 196,104 KB |
最終ジャッジ日時 | 2025-01-12 10:13:45 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 9 WA * 3 |
ソースコード
#include <bits/stdc++.h>#define _overload3(_1, _2, _3, name, ...) name#define _rep(i, n) repi(i, 0, n)#define repi(i, a, b) for (int i = (a); i < (b); ++i)#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)#define ALL(x) x.begin(), x.end()#define chmax(x, y) x = max(x, y)#define chmin(x, y) x = min(x, y)using namespace std;random_device rnd;mt19937 mt(rnd());using ll = long long;using lld = long double;using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;using PII = pair<int, int>;const int IINF = 1 << 30;const ll INF = 1ll << 60;ll frac(int n, int m){if (n == 0)return 1;return (frac(n - 1, m) * n) % m;;}vector<bool> make_prime(){vector<bool> isPrime(5 * 1010101, true);isPrime[0] = false;isPrime[1] = false;rep(i, 2, 5 * 1010101){if (isPrime[i] == false){continue;}for (int j = i + i; j < 5 * 1010101; j += i){isPrime[j] = false;}}return isPrime;}ll mpow(ll base, ll num, ll mod){if (num == 0)return 1;ll prev = mpow(base, num / 2, mod);if (num % 2 == 0){return (prev * prev) % mod;}else{return (((prev * prev) % mod) * base) % mod;}}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);auto isPrime = make_prime();int t;cin >> t;rep(i, t){ll a, p;cin >> a >> p;if (isPrime[p]){cout << mpow(a, p - 1, p) << endl;}else{cout << -1 << "\n";}}return 0;}