結果
問題 | No.1140 EXPotentiaLLL! |
ユーザー |
|
提出日時 | 2020-07-31 22:02:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,220 bytes |
コンパイル時間 | 1,653 ms |
コンパイル使用メモリ | 172,140 KB |
実行使用メモリ | 24,852 KB |
最終ジャッジ日時 | 2024-07-06 18:08:06 |
合計ジャッジ時間 | 5,574 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 9 WA * 3 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) using namespace std; using ll = long long ; using P = pair<int,int> ; using pll = pair<long long,long long>; constexpr int INF = 1e9; constexpr long long LINF = 1e17; constexpr int MOD = 1000000007; constexpr double PI = 3.14159265358979323846; struct Sieve { int n; vector<int> f,primes; Sieve(int n=1):n(n),f(n+1){ f[0] = f[1] = -1; for(long long i=2;i<=n;++i){ if(f[i]) continue; primes.push_back(i); f[i] = i; for(long long j = i*i;j <= n;j += i) { if(!f[j]) f[j] = i; } } } bool isPrime(int x){return f[x] == x;} vector<int> factorList(int x){ vector<int> res; while(x != 1){ res.push_back(f[x]); x /= f[x]; } return res; } vector<pair<int,int>> factor(int x){ vector<int> fl = factorList(x); if(fl.size() == 0) return {}; vector<pair<int,int>> res(1,pair<int,int>(fl[0],0)); for(int p:fl){ if(res.back().first == p){ res.back().second ++; }else{ res.emplace_back(p,1); } } return res; } long long divisorCalc(long long x){ long long res = 1; long long now = -1; long long nowCnt = 0; while(x != 1){ if(now==f[x]) ++ nowCnt; else{ res *= nowCnt + 1; now = f[x]; nowCnt = 1; } x /= f[x]; } res *= nowCnt+1; return res; } }; int main(){ Sieve sieve(5000005); int t; scanf("%d",&t); while(t--){ int a,p; scanf("%d %d",&a,&p); if(sieve.isPrime(p)){ if(a%p==0) printf("%d\n",0); else printf("%d\n",1); } else printf("%d\n",-1); } return 0; }