結果
問題 |
No.1140 EXPotentiaLLL!
|
ユーザー |
|
提出日時 | 2021-01-30 09:03:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 203 ms / 2,000 ms |
コード長 | 1,271 bytes |
コンパイル時間 | 2,376 ms |
コンパイル使用メモリ | 197,840 KB |
最終ジャッジ日時 | 2025-01-18 09:51:02 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 12 |
ソースコード
typedef long long ll; typedef long double ld; #include <bits/stdc++.h> using namespace std; template< typename T > T mod_pow(T x, T n, const T &p) { T ret = 1; while(n > 0) { if(n & 1) (ret *= x) %= p; (x *= x) %= p; n >>= 1; } return ret; } std::vector<bool> IsPrime; void sieve(size_t max){ if(max+1 > IsPrime.size()){ // resizeで要素数が減らないように IsPrime.resize(max+1,true); // IsPrimeに必要な要素数を確保 } IsPrime[0] = false; // 0は素数ではない IsPrime[1] = false; // 1は素数ではない for(size_t i=2; i*i<=max; ++i) // 0からsqrt(max)まで調べる if(IsPrime[i]) // iが素数ならば for(size_t j=2; i*j<=max; ++j) // (max以下の)iの倍数は IsPrime[i*j] = false; // 素数ではない } int main() { sieve(5000000); cin.tie(nullptr); ios::sync_with_stdio(false); ll t; std::cin >> t; for (int di = 0; di < t; di++) { ll a,p; std::cin >> a>>p; if(IsPrime[p]){ if(a%p==0){ std::cout << 0 << '\n'; continue; } std::cout << 1 << '\n'; }else{ std::cout << -1 << '\n'; } } }