結果
問題 | No.1113 二つの整数 / Two Integers |
ユーザー |
![]() |
提出日時 | 2020-07-20 14:05:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 2,877 bytes |
コンパイル時間 | 1,619 ms |
コンパイル使用メモリ | 181,068 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-23 15:24:19 |
合計ジャッジ時間 | 2,302 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 15 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)#define all(x) (x).begin(), (x).end()#define rall(x) (x).rbegin(), (x).rend()#define sz(x) ((ll)(x).size())#define len(x) ((ll)(x).length())#define endl "\n"struct Factorize {private:unsigned long long modmul(unsigned long long a, unsigned long long b, unsigned long long M) {long long ret = a * b - M * (unsigned long long)(1.L / M * a * b);return ret + M * (ret < 0) - M * (ret >= (long long)M);}unsigned long long modpow(unsigned long long b, unsigned long long e, unsigned long long mod) {unsigned long long ans = 1;for (; e; b = modmul(b, b, mod), e /= 2)if (e & 1) ans = modmul(ans, b, mod);return ans;}bool isPrime(unsigned long long n) {if (n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;unsigned long long A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};unsigned long long s = __builtin_ctzll(n-1), d = n >> s;for (unsigned long long a : A) {unsigned long long p = modpow(a%n, d, n), i = s;while (p != 1 && p != n - 1 && a % n && i--)p = modmul(p, p, n);if (p != n-1 && i != s) return 0;}return 1;}unsigned long long pollard(unsigned long long n) {auto f = [&](unsigned long long x) { return modmul(x, x, n) + 1; };unsigned long long x = 0, y = 0, t = 0, prd = 2, i = 1, q;while (t++ % 40 || __gcd(prd, n) == 1) {if (x == y) x = ++i, y = f(x);if ((q = modmul(prd, max(x,y) - min(x,y), n))) prd = q;x = f(x), y = f(f(y));}return __gcd(prd, n);}vector<unsigned long long> factor(unsigned long long n) {if (n == 1) return {};if (isPrime(n)) return {n};unsigned long long x = pollard(n);auto l = factor(x), r = factor(n / x);l.insert(l.end(), r.begin(), r.end());return l;}public:template<typename T>map<T, int> get_map(T n) {auto fac = factor(n);map<T, int> res;for(auto &x : fac) res[(T)x]++;return res;}};int main() {cin.tie(0);ios::sync_with_stdio(false);// ifstream in("input.txt");// cin.rdbuf(in.rdbuf());ll a, b;cin >> a >> b;Factorize fac;auto fa = fac.get_map(a);auto fb = fac.get_map(b);ll cnt = 1;for(auto &x : fa) {cnt *= min(x.second, fb[x.first]) + 1;}cout << ((cnt % 2 == 0) ? "Even" : "Odd") << endl;return 0;}