結果
問題 |
No.1140 EXPotentiaLLL!
|
ユーザー |
|
提出日時 | 2020-07-31 21:31:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,859 ms / 2,000 ms |
コード長 | 1,060 bytes |
コンパイル時間 | 1,221 ms |
コンパイル使用メモリ | 106,416 KB |
最終ジャッジ日時 | 2025-01-12 09:13:11 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 12 |
ソースコード
#include <iostream> #include <algorithm> #include <map> #include <set> #include <queue> #include <stack> #include <numeric> #include <bitset> #include <cmath> static const int MOD = 1000000007; using ll = long long; using u32 = unsigned; using u64 = unsigned long long; using namespace std; template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208; vector<bool> is_prime; vector<int> get_prime(int n){ if(n <= 1) return vector<int>(); is_prime.resize(n+1, true); vector<int> prime; is_prime[0] = is_prime[1] = 0; for (int i = 2; i <= n; ++i) { if(is_prime[i]) prime.emplace_back(i); for (auto &&j : prime){ if(i*j > n) break; is_prime[i*j] = false; if(i % j == 0) break; } } return prime; } auto v = get_prime(5000001); void solve(){ ll a, p; cin >> a >> p; a %= p; if(is_prime[p]) { puts(a == 0 ? "0" : "1"); }else puts("-1"); } int main() { int t; cin >> t; while(t--){ solve(); } return 0; }