結果
問題 | No.2724 Coprime Game 1 |
ユーザー | 👑 binap |
提出日時 | 2024-04-12 23:23:33 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,561 bytes |
コンパイル時間 | 2,383 ms |
コンパイル使用メモリ | 211,656 KB |
実行使用メモリ | 39,588 KB |
最終ジャッジ日時 | 2024-10-02 23:49:56 |
合計ジャッジ時間 | 4,017 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 50 ms
39,452 KB |
testcase_01 | AC | 51 ms
39,456 KB |
testcase_02 | WA | - |
testcase_03 | AC | 215 ms
39,460 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
ソースコード
#include<bits/stdc++.h> #define rep(i,n) for(int i=0;i<n;i++) using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<long long> vl; typedef vector<vector<int>> vvi; typedef vector<vector<long long>> vvl; typedef pair<int,int> P; typedef long double ld; template<typename T>istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;} template<typename U, typename T> ostream& operator<<(ostream& os, const pair<U, T>& p){os << p.first << ' ' << p.second; return os;} template<typename T>ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return os;} template <typename T>ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); return os;} template<typename T> void chmin(T& a, T b){a = min(a, b);} template<typename T> void chmax(T& a, T b){a = max(a, b);} // Sieve of Eratosthenes // https://youtu.be/UTVg7wzMWQc?t=2774 struct Sieve { int n; vector<int> f, primes; Sieve(int n=1):n(n), f(n+1) { f[0] = f[1] = -1; for (ll i = 2; i <= n; ++i) { if (f[i]) continue; primes.push_back(i); f[i] = i; for (ll 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<ll,int>> factor(ll x) { vector<pair<ll,int>> res; for (int p : primes) { int y = 0; while (x%p == 0) x /= p, ++y; if (y != 0) res.emplace_back(p,y); } if (x != 1) res.emplace_back(x,1); return res; } int num_of_divisors(long long x){ auto f = factor(x); long long res = 1; for(auto [p, val] : f){ res *= val + 1; } return res; } set<long long> divisors(long long x){ set<long long> se = {1}; auto f = factor(x); for(auto [key, value] : f){ set<long long> old = se; for(long long y : old){ rep(i, value + 1){ se.insert(y); y *= key; } } } return se; } }; const int M = 3000000; vector<int> f(M + 1); vector<int> g(M + 1); Sieve sieve(M + 1); int solve(){ int n; cin >> n; int m = n - (f[n - 1] - f[n / 2]) - 2; if(m % 2) cout << "K\n"; else cout << "P\n"; return 0; } int main(){ for(int x = 1; x <= M; x++){ f[x] = f[x - 1]; if(sieve.isPrime(x)) f[x]++; } int t; cin >> t; rep(_, t) solve(); return 0; }