結果
問題 | No.2 素因数ゲーム |
ユーザー | xoke0114 |
提出日時 | 2019-03-13 17:03:44 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 7,370 bytes |
コンパイル時間 | 1,643 ms |
コンパイル使用メモリ | 179,772 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-08 00:56:47 |
合計ジャッジ時間 | 2,517 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 1 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 2 ms
5,376 KB |
testcase_30 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define M_PI 3.14159265358979323846 using ull = unsigned long long; using ll = long long; #define endl "\n" #define REP(i, n) for (ll i = 0; i < n; i++) #define REPR(i, n) for (ll i = n; i >= 0; i--) #define FOR(i, m, n) for (ll i = m; i < n; i++) #define even(x) (x) % 2 == 0 #define odd(x) (x) % 2 != 0 #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define pcnt __builtin_popcount #define buli(x) __builtin_popcountll(x) #define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()); #define inll(x) ll x;cin>>x; #define INIT() cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(20) // these functions return the position of result of Binary Search. #define LB(s, t, x) (int)(lower_bound(s, t, x) - s) #define UB(s, t, x) (int)(upper_bound(s, t, x) - s) namespace { const ll MOD_CONST = (ll)(1e9 + 7); const ll CFM = (ll)(998244353); ll qp(ll a, ll b, int mo) { ll ans = 1; do { if (b & 1) ans = 1ll * ans * a % mo; a = 1ll * a * a % mo; } while (b >>= 1); return ans; } ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { ll temp = gcd(a, b); return temp ? (a / temp * b) : 0; } int mDays[] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; int dx8[] = {1, -1, 0, 0, 1, 1, -1, -1}, dy8[] = {0, 0, -1, 1, -1, 1, -1, 1}; template <typename F> class #if defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard) [[nodiscard]] #elif defined(__GNUC__) && __GNUC_PREREQ(3, 4) __attribute__((warn_unused_result)) #endif // defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard) FixPoint : F { public : explicit constexpr FixPoint(F &&f) noexcept : F(std::forward<F>(f)) {} template <typename... Args> constexpr decltype(auto) operator()(Args &&... args) const { return F::operator()(*this, std::forward<Args>(args)...); } // namespace } ; // class FixPoint template <typename F> static inline constexpr decltype(auto) makeFixPoint(F &&f) noexcept { return FixPoint<F>{std::forward<F>(f)}; } template <typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template <typename T, typename... Ts> auto make_v(size_t a, size_t b, Ts... ts) { return vector<decltype(make_v<T>(b, ts...))>(a, make_v<T>(b, ts...)); } template <typename T, typename V> typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) { t = v; } template <typename T, typename V> typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) { for (auto &e : t) fill_v(e, v); } 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; } inline tuple<ll, ll> rotate45(tuple<ll, ll> point) { ll x = get<0>(point), y = get<1>(point); return tuple<ll, ll>(x + y, x - y); } inline bool rangeCheck2D(int nx, int ny, int Width, int Height) { return nx >= 0 and nx < Width and ny >= 0 and ny < Height; } template <class T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto i = begin(v); i != end(v); ++i) os << *i << (i == end(v) - 1 ? "" : " "); return os; } template <class T> istream &operator>>(istream &is, vector<T> &v) { for (auto i = begin(v); i != end(v); ++i) is >> *i; return is; } template <typename T> void out(T o) { cout << o << endl; } template <typename T> void out(vector<T> &out) { REP(i, (int)out.size()) { cout << out[i]; if (i == (int)out.size() - 1) cout << endl; else cout << " "; } } template <typename T> void out(vector<vector<T>> o) { REP(i, o.size()) out(o[i]); } ll i_query(ll x) { cout << "> " << x << endl; fflush(stdout); ll ret; cin >> ret; return ret; } ll i_query_2(ll i) { cout << "? " << i << endl; fflush(stdout); ll ret; cin >> ret; return ret; } void i_answer(ll ans, ll d) { cout << "! " << ans << " " << d << endl; fflush(stdout); } } // namespace // lambda expression // auto f = [](int arg1, double arg2) { return ret; }; // lambda recursion // auto result = makeFixPoint([&](auto rec, int pos, int v) -> int { // rec(pos, v); // })(0, 1); // auto func = makeFixPoint([]() -> int {}); // int ret = func(); // tuple binding // auto [x, y] = make_tuple(0, 0); // for pair // auto [a, b] = pair<int, int>({v1, v2}); // bitset<N> bs(ini_val); // N must be constant // bs.reset(); // reset all namespace PrimeLib { //* 素数判定 is_prime<unsigned>(N) template<typename T, std::enable_if_t<std::is_unsigned<T>::value, std::nullptr_t> = nullptr> bool is_prime(const T n) { if (n < 4) return n == 2 || n == 3; if (n % 2 == 0 || n % 3 == 0 || (n % 6 != 1 && n % 6 != 5)) return false; for (T i = 5; i * i <= n; i += 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } //* 素数テーブル生成 エラトステネスの篩 10^7 => 1s //* 1e9を素因数分解したい時,sqrt(1e9)まで(31623程)を生成すればよい vector<ll> primeTable(ll n) { vector<bool> table(n - 1); vector<ll> ret; for (ll i = 0; i < n - 1; ++i) { if (table[i] == false) { ll num = i + 2; ret.push_back(i + 2); for (int j = i + num; j < n - 1; j += num) table[j] = true; } } return ret; } vector<pair<ll, ll>> factorize(ll n) { vector<pair<ll, ll>> ps; for (ll i = 2; i * i <= n; i++) { if (n % i == 0) { int cnt = 0; while (n % i == 0) { n /= i; cnt++; } ps.emplace_back(i, cnt); } } //assert(c == 1); // if c is still not 1, // there's one prime num bigger than sqrt(N) if (n > 1) ps.emplace_back(n, 1); return ps; } // 約数列挙 std::vector<ll> divisors(ll n) { std::vector<ll> ret; for(ll i=1 ; i*i<=n ; ++i) { if(n%i == 0) { ret.push_back(i); if(i!=1 && i*i!=n) { ret.push_back(n/i); } } } if (n > 1) ret.push_back(n); sort(all(ret)); return ret; } } int main(void) { INIT(); // comment out for Interective Program inll(N); auto ps = PrimeLib::factorize(N); ll nim = 0; REP(i, ps.size()) { nim ^= ps[i].second; } if (nim == 0) out("Bob"); else out("Alice"); return 0; } //*/