結果
問題 | No.2725 Coprime Game 2 |
ユーザー | GOTKAKO |
提出日時 | 2024-04-12 22:50:47 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,123 bytes |
コンパイル時間 | 2,368 ms |
コンパイル使用メモリ | 210,328 KB |
実行使用メモリ | 10,496 KB |
最終ジャッジ日時 | 2024-10-02 23:38:42 |
合計ジャッジ時間 | 5,826 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
10,496 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 9 ms
5,248 KB |
testcase_03 | AC | 144 ms
5,248 KB |
testcase_04 | TLE | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int Need = 100; vector<vector<pair<int,int>>> Pf(Need+1); vector<bool> prime(Need+1,true); prime.at(0) = false; prime.at(1) = false; for(int i=2; i<=Need; i++){ if(!prime.at(i)) continue; Pf.at(i) = {{i,1}}; for(int k=i+i; k<=Need; k+=i){ prime.at(k) = false; int f = 0,k2 = k; while(k2%i == 0) f++,k2 /= i; Pf.at(k).push_back({i,f}); } } int T; cin >> T; while(T--){ long long N; cin >> N; if(N == 2){cout << "P" << endl; continue;} int first = -1; for(int i=2; i<=N; i++){ if(N%i == 0) continue; first = i; break; } int now = first,yes = 0,add = 1; for(auto [p,e] : Pf.at(now)) add *= p; while(now < N){ int g = gcd(now,N); if(g == 1 && N%now){yes = 1; break;} now += add; } if(yes) cout << "K" << endl; else cout << "P" << endl; } }