結果
問題 |
No.2 素因数ゲーム
|
ユーザー |
|
提出日時 | 2023-01-04 14:36:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 1,457 bytes |
コンパイル時間 | 1,131 ms |
コンパイル使用メモリ | 111,472 KB |
最終ジャッジ日時 | 2025-02-09 23:13:10 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
#include <iostream> #include <algorithm> #include <iomanip> #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<int> get_prime(int n){ if(n <= 1) return vector<int>(); vector<bool> is_prime(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; } const auto primes = get_prime(10000); template<class T> vector<T> prime_factor(T n){ vector<T> res; for (auto &&i : primes) { while (n % i == 0){ res.emplace_back(i); n /= i; } } if(n != 1) res.emplace_back(n); return res; } int main() { int n; cin >> n; auto v = prime_factor(n); vector<pair<int, int>> u; u.emplace_back(v[0], 1); for (int i = 1; i < v.size(); ++i) { if(u.back().first == v[i]) u.back().second++; else u.emplace_back(v[i], 1); } int ans = 0; for (auto &&i : u) ans ^= i.second; puts(ans ? "Alice" : "Bob"); return 0; }