結果
問題 | No.2 素因数ゲーム |
ユーザー | shirokami |
提出日時 | 2023-04-13 14:41:00 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 3,919 bytes |
コンパイル時間 | 5,646 ms |
コンパイル使用メモリ | 334,248 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-09 12:34:21 |
合計ジャッジ時間 | 6,727 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,820 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 3 ms
5,248 KB |
testcase_14 | AC | 2 ms
5,248 KB |
testcase_15 | AC | 2 ms
5,248 KB |
testcase_16 | AC | 2 ms
5,248 KB |
testcase_17 | AC | 2 ms
5,248 KB |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | AC | 2 ms
5,248 KB |
testcase_20 | AC | 2 ms
5,248 KB |
testcase_21 | AC | 2 ms
5,248 KB |
testcase_22 | AC | 2 ms
5,248 KB |
testcase_23 | AC | 2 ms
5,248 KB |
testcase_24 | AC | 2 ms
5,248 KB |
testcase_25 | AC | 2 ms
5,248 KB |
testcase_26 | AC | 2 ms
5,248 KB |
testcase_27 | AC | 2 ms
5,248 KB |
testcase_28 | AC | 2 ms
5,248 KB |
testcase_29 | AC | 2 ms
5,248 KB |
testcase_30 | AC | 2 ms
5,248 KB |
ソースコード
#include <bits/extc++.h> using namespace std; // using namespace __gnu_pbds; // #include <boost/multiprecision/cpp_int.hpp> // using Bint = boost::multiprecision::cpp_int; // #include <atcoder/all> // using namespace atcoder; // https://atcoder.github.io/ac-library/production/document_ja/ typedef long long int ll; typedef long double ld; constexpr ll mod = 1e9+7; constexpr ll INF = 9'223'372'036'854'775'807/10; #define rep(i,n) for (ll i = 0; i < (n); ++i) #define Rep(i,a,n) for (ll i = (a); i < (n); ++i) #define All(a) (a).begin(),(a).end() #define Pi acos(-1) using V = vector<ll>; using P = pair<ll,ll>; vector<ll> dx = {1, 0, -1, 0, 1, 1, -1, -1}; vector<ll> dy = {0, 1, 0, -1, 1, -1, 1, -1}; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } struct edge{ll to, cost;}; using graph = vector<vector<edge> >; struct IoSetup { IoSetup() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << setprecision(15) << fixed; } } iosetup; void print(vector<string> &v) { for (string s : v) { cout << s << '\n'; } } template<typename T> void print(vector<T> &v, int w = 0) { for (int i = 0; i < (int)v.size(); i++) { cout << right << setw(w) << v[i] << " \n"[i == (int)v.size() - 1]; } } template<typename T> void print(vector<vector<T>> &v, int w = 0) { for (int i = 0; i < (int)v.size(); i++) { print(v[i], w); } } __int128_t pow_mod_128(__int128_t A, __int128_t N, __int128_t M) { __int128_t res = 1 % M; A %= M; while (N) { if (N & 1) res = (res * A) % M; A = (A * A) % M; N >>= 1; } return res; } bool is_prime(long long N) { if (N <= 1) return false; if (N == 2) return true; if (N % 2 == 0) return false; vector<long long> A = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}; long long s = 0, d = N - 1; while (d % 2 == 0) { ++s; d >>= 1; } for (auto a : A) { if (a % N == 0) return true; long long t, x = pow_mod_128(a, d, N); if (x != 1) { for (t = 0; t < s; ++t) { if (x == N - 1) break; x = __int128_t(x) * x % N; } if (t == s) return false; } } return true; } long long pollard(long long N) { if (N % 2 == 0) return 2; if (is_prime(N)) return N; auto f = [&](long long x) -> long long { return (__int128_t(x) * x + 1) % N; }; long long step = 0; while (true) { ++step; long long x = step, y = f(x); while (true) { long long p = gcd(y - x + N, N); if (p == 0 || p == N) break; if (p != 1) return p; x = f(x); y = f(f(y)); } } } vector<long long> prime_factorize(long long N) { if (N == 1) return {}; long long p = pollard(N); if (p == N) return {p}; vector<long long> left = prime_factorize(p); vector<long long> right = prime_factorize(N / p); left.insert(left.end(), right.begin(), right.end()); sort(left.begin(), left.end()); return left; } vector<pair<long long, long long>> prime_factorize_pair(long long N) { vector<long long> left = prime_factorize(N); left.push_back(-1); vector<pair<long long, long long>> g; long long cnt = 1; for (int i = 1; i < (int)left.size(); i++) { if (left[i] == left[i-1]) { cnt++; } else { g.push_back({left[i-1], cnt}); cnt = 1; } } return g; } /* prime_factorize: 素因数を列挙した配列で返す prime_factorize_pair: {素因数, 乗数} を格納した配列で返す 例 prime_factorize 12 -> {2, 2, 3} 2 -> {2} 1 -> {} prime_factorize_pair 12 -> {{2, 2}, {3, 1}} 2 -> {{2, 1}} 1 -> {} */ int main() { ll n; cin >> n; auto p = prime_factorize_pair(n); vector<ll> a; for (auto x : p) { a.push_back(x.second); } ll ans = 0; rep(i,a.size()) { ans ^= a[i]; } cout << (ans ? "Alice" : "Bob") << endl; }