結果
問題 | No.1140 EXPotentiaLLL! |
ユーザー |
![]() |
提出日時 | 2020-07-31 23:41:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,003 bytes |
コンパイル時間 | 1,596 ms |
コンパイル使用メモリ | 170,276 KB |
実行使用メモリ | 16,000 KB |
最終ジャッジ日時 | 2024-07-06 21:55:18 |
合計ジャッジ時間 | 6,142 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 3 WA * 9 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i=(0);i<(n);i++)using namespace std;typedef long long ll;template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }bool isprime[5000001];ll powmod(ll a, ll b, ll p){if(b == 0) return 1;if(b & 1) {return a * powmod(a, b - 1, p) % p;} else {ll d = powmod(a, b / 2, p) % p;return d * d % p;}}ll solve(ll a, ll p){if(!isprime[p]) return -1;if(a % p == 0) return 0;ll ret = powmod(a, p, p);return ret * (p - 1) % p;}int main(){cin.tie(0);ios::sync_with_stdio(false);rep(i, 5000001) isprime[i] = true;isprime[0] = isprime[1] = false;for(int i = 2; i <= 5000000; i++){if(!isprime[i]) continue;for(int j = 2 * i; j <= 5000000; j += i) isprime[j] = false;}ll t;cin >> t;vector<ll> a(t), p(t);rep(i, t) cin >> a[i] >> p[i];rep(i, t) cout << solve(a[i], p[i]) << "\n";}