結果
問題 |
No.1140 EXPotentiaLLL!
|
ユーザー |
![]() |
提出日時 | 2020-08-09 00:47:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 269 ms / 2,000 ms |
コード長 | 1,950 bytes |
コンパイル時間 | 2,569 ms |
コンパイル使用メモリ | 192,828 KB |
最終ジャッジ日時 | 2025-01-12 19:11:25 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 12 |
ソースコード
#ifndef _TEMPLATE_ROOT #define _TEMPLATE_ROOT #include "bits/stdc++.h" using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define repl(i, a, b) for(ll i = a; i < (b); ++i) #define repd(i, a, b) for(int i = b; i >= (a); --i) #define repdl(i, a, b) for(ll i = b; i >= (a); --i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; template<typename H> bool chmin(H& v1, const H v2) { if (v1 > v2) { v1 = v2; return true; } return false; } template<typename H> bool chmax(H& v1, const H v2) { if (v1 < v2) { v1 = v2; return true; } return false; } #endif #ifndef _TEMPLATE_IO #define _TEMPLATE_IO template<typename H> void read(H& head) { cin >> head; } template<typename H, typename ...T> void read(H& head, T& ...tail) { cin >> head; read(tail...); } template<typename H> void write(H head) { cout << head << '\n'; } template<typename H, typename ...T> void write(H head, T ...tail) { cout << head << " "; write(tail...); } template<typename ...T> void writef(T ...tail) { write(tail...); cout << flush; } template<typename ...T> void die(T ...tok) { write(tok...); exit(0); } template<typename T> ostream& operator<<(ostream& out, const vector<T>& v) { if (v.size()) { rep(i, 0, sz(v) - 1) out << v[i] << " "; out << v.back(); } return out; } #endif using namespace std; bitset<5000005> sieve; ll bm(ll b, ll p, ll m) { ll r = 1; for (; p; p >>= 1, b = b * b % m) if (p & 1) r = r * b % m; return r; } int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); sieve.set(); sieve[0] = sieve[1] = false; for (int i = 2; i * i < 5000005; i++) for (int j = i * i; j < 5000005; j += i) sieve[j] = false; int n; read(n); rep(i, 0, n) { ll a, p; read(a, p); a %= p; if (!sieve[p]) write(-1); else if (a == 0) write(0); else write(1); } }