結果
問題 | No.2 素因数ゲーム |
ユーザー | Shuz* |
提出日時 | 2019-07-22 16:02:54 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 7,347 bytes |
コンパイル時間 | 2,629 ms |
コンパイル使用メモリ | 197,716 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-23 18:36:46 |
合計ジャッジ時間 | 3,424 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 3 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,944 KB |
testcase_13 | AC | 2 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 2 ms
6,944 KB |
testcase_16 | AC | 2 ms
6,944 KB |
testcase_17 | AC | 2 ms
6,944 KB |
testcase_18 | AC | 2 ms
6,944 KB |
testcase_19 | AC | 2 ms
6,944 KB |
testcase_20 | AC | 2 ms
6,940 KB |
testcase_21 | AC | 2 ms
6,944 KB |
testcase_22 | AC | 2 ms
6,940 KB |
testcase_23 | AC | 2 ms
6,940 KB |
testcase_24 | AC | 2 ms
6,944 KB |
testcase_25 | AC | 2 ms
6,944 KB |
testcase_26 | AC | 2 ms
6,944 KB |
testcase_27 | AC | 2 ms
6,940 KB |
testcase_28 | AC | 2 ms
6,940 KB |
testcase_29 | AC | 2 ms
6,940 KB |
testcase_30 | AC | 2 ms
6,944 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; // Define using ll = long long; using ull = unsigned long long; using ld = long double; const ll dx[4] = {1, 0, -1, 0}; const ll dy[4] = {0, 1, 0, -1}; const ll MOD = 1e9 + 7; const ll mod = 998244353; const ll inf = 1 << 30; const ll LINF = LONG_MAX; const ll INF = 1LL << 60; const ull MAX = ULONG_MAX; #define mp make_pair #define pb push_back #define elif else if #define endl '\n' #define space ' ' #define def inline auto #define func inline constexpr ll #define run(a) __attribute__((constructor)) def _##a() #define all(v) begin(v), end(v) #define rall(v) rbegin(v), rend(v) #define input(a) scanf("%lld", &(a)) #define print(a) printf("%lld\n", (a)) #define fi first #define se second #define ok(a, b) (0 <= (a) && (a) < (b)) #define modulo(a, b) ((a % b + b) % b) template <class T> using vvector = vector<vector<T>>; template <class T> using pvector = vector<pair<T, T>>; template <class T> using rpriority_queue = priority_queue<T, vector<T>, greater<T>>; 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 (a > b) { a = b; return 1; } return 0; } // Debug #define debug(...) \ { \ cerr << __LINE__ << ": " << #__VA_ARGS__ << " = "; \ for (auto &&X : {__VA_ARGS__}) cerr << "[" << X << "] "; \ cerr << endl; \ } #define dump(a, h, w) \ { \ cerr << __LINE__ << ": " << #a << " = [" << endl; \ rep(__i, h) { \ rep(__j, w) cerr << a[__i][__j] << space; \ cerr << endl; \ } \ cerr << "]" << endl; \ } #define vdump(a, n) \ { \ cerr << __LINE__ << ": " << #a << " = ["; \ rep(__i, n) if (__i) cerr << space << a[__i]; \ else cerr << a[__i]; \ cerr << "]" << endl; \ } // Loop #define inc(i, a, n) for (ll i = (a), _##i = (n); i <= _##i; ++i) #define dec(i, a, n) for (ll i = (a), _##i = (n); i >= _##i; --i) #define rep(i, n) for (ll i = 0, _##i = (n); i < _##i; ++i) #define each(i, a) for (auto &&i : a) #define loop() for (;;) // Stream #define fout(n) cout << fixed << setprecision(n) #define fasten cin.tie(0), ios::sync_with_stdio(0) run(0) { fasten, fout(10); } // Speed #pragma GCC optimize("O3") #pragma GCC target("avx") // Math func gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } func lcm(ll a, ll b) { return a * b / gcd(a, b); } func sign(ll a) { return a ? abs(a) / a : 0; } struct Factorize { #define MAXL (50000 >> 5) + 1 #define GET(x) (mark[x >> 5] >> (x & 31) & 1) #define SET(x) (mark[x >> 5] |= 1 << (x & 31)) int mark[MAXL]; int P[50000], Pt = 0; void sieve() { int i, j, k; SET(1); int n = 46340; for (i = 2; i <= n; i++) { if (!GET(i)) { for (k = n / i, j = i * k; k >= i; k--, j -= i) SET(j); P[Pt++] = i; } } } ll mul(ull a, ull b, ull mod) { ll ret = 0; for (a %= mod, b %= mod; b != 0; b >>= 1, a <<= 1, a = a >= mod ? a - mod : a) { if (b & 1) { ret += a; if (ret >= mod) ret -= mod; } } return ret; } void exgcd(ll x, ll y, ll &g, ll &a, ll &b) { if (y == 0) g = x, a = 1, b = 0; else exgcd(y, x % y, g, b, a), b -= (x / y) * a; } ll llgcd(ll x, ll y) { if (x < 0) x = -x; if (y < 0) y = -y; if (!x || !y) return x + y; ll t; while (x % y) t = x, x = y, y = t % y; return y; } ll inverse(ll x, ll p) { ll g, b, r; exgcd(x, p, g, r, b); if (g < 0) r = -r; return (r % p + p) % p; } ll mpow(ll x, ll y, ll mod) { // mod < 2^32 ll ret = 1; while (y) { if (y & 1) ret = (ret * x) % mod; y >>= 1, x = (x * x) % mod; } return ret % mod; } ll mpow2(ll x, ll y, ll mod) { ll ret = 1; while (y) { if (y & 1) ret = mul(ret, x, mod); y >>= 1, x = mul(x, x, mod); } return ret % mod; } int isPrime(ll p) { // implements by miller-babin if (p < 2 || !(p & 1)) return 0; if (p == 2) return 1; ll q = p - 1, a, t; int k = 0, b = 0; while (!(q & 1)) q >>= 1, k++; for (int it = 0; it < 2; it++) { a = rand() % (p - 4) + 2; t = mpow2(a, q, p); b = (t == 1) || (t == p - 1); for (int i = 1; i < k && !b; i++) { t = mul(t, t, p); if (t == p - 1) b = 1; } if (b == 0) return 0; } return 1; } ll pollard_rho(ll n, ll c) { ll x = 2, y = 2, i = 1, k = 2, d; while (true) { x = (mul(x, x, n) + c); if (x >= n) x -= n; d = llgcd(x - y, n); if (d > 1) return d; if (++i == k) y = x, k <<= 1; } return n; } void factorize(int n, vector<ll> &f) { for (int i = 0; i < Pt && P[i] * P[i] <= n; i++) { if (n % P[i] == 0) { while (n % P[i] == 0) f.push_back(P[i]), n /= P[i]; } } if (n != 1) f.push_back(n); } void llfactorize(ll n, vector<ll> &f) { if (n == 1) return; if (n < 2e+9) { factorize(n, f); return; } if (isPrime(n)) { f.push_back(n); return; } ll d = n; for (int i = 2; d == n; i++) d = pollard_rho(n, i); llfactorize(d, f); llfactorize(n / d, f); } vector<ll> factors(ll n) { vector<ll> f; map<ll, int> r; llfactorize(n, f); for (auto &x : f) r[x]++; vector<ll> ret; for (auto it = r.begin(); it != r.end(); it++) { for (int i = 0; i < it->second; i++) ret.push_back(it->first); } return ret; } vector<ll> factorize(ll n) { sieve(); return factors(n); } }; signed main() { ll N, res = 0; cin >> N; Factorize F; vector<ll> A = F.factorize(N); map<ll, ll> M; rep(i, A.size()) M[A[i]]++; each(i, M) res ^= i.se; cout << (res ? "Alice" : "Bob") << endl; }