結果

問題 No.1113 二つの整数 / Two Integers
ユーザー hamrayhamray
提出日時 2020-07-17 22:06:32
言語 C++11
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 3,450 bytes
コンパイル時間 1,631 ms
コンパイル使用メモリ 160,880 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-11-30 00:10:32
合計ジャッジ時間 10,416 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 11 TLE * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
 
const double pi = 3.141592653589793238462643383279;
using namespace std;
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
 
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
 
//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
 
 
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
 
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const double EPS = 1E-10;
 
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)


//ここから編集
ll GCD(ll a, ll b){
    
    if(b == 0) return a;
    return GCD(b, a%b);
}
using Int32 = __int32_t;
using Int64 = __int64_t;
using Int128 = __int128_t;
using ll = long long int;
Int128 powmod(Int128 x, Int128 n, ll mod)
{
    Int128 res = 1;
    while (n > 0)
    {

        if (n & 1)
        {
            res = (res * x) % mod;
        }
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

Int128 mulmod(Int128 a, Int128 b, ll mod)
{
    Int128 x = 0, y = a % mod;
    while (b > 0)
    {

        if (b % 2 == 1)
        {
            x = (x + y) % mod;
        }

        y = (y * 2) % mod;
        b /= 2;
    }
    return x % mod;
}
ll gcd(ll a, ll b)
{
    if (a < b)
        std::swap(a, b);

    while (b > 0)
    {
        ll tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}

inline ll funct(ll x, ll c)
{
    return x * x + c;
}

bool MillerRabinTest(Int128 n)
{
    constexpr Int128 witness[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, -1};
    if (n == 2)
        return true;

    if (n <= 1 || n % 2 == 0)
        return false;

    Int128 d = n - 1;
    int s = 0;
    while (!(d & 1))
    {
        ++s;
        d >>= 1;
    }

    for (int i = 0; witness[i] != -1 && witness[i] < n; i++)
    {
        Int128 y = powmod(witness[i], d, n);

        if (y == 1)
            continue;

        for (int j = 0; j < s - 1 && y != n - 1; j++)
            y = mulmod(y, y, n);

        if (y != n - 1)
            return false;
    }
    return true;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  ll A, B; cin >> A >> B;

  ll d = GCD(A, B);

  if(d == 1){
    cout << "Odd" << endl;
  }else{
    for(ll i=2; i*i<=d; i++){
      if(d%i == 0){
        ll cnt = 0;
        while(d%i == 0){
          d/=i;
          cnt++;
        }
        if(cnt%2 == 1){
          cout << "Even" << endl;
          return 0;
        }
      }
      if(MillerRabinTest(d)){
        break;
      }
    }if(d!=1){
        cout << "Even" << endl;
        return 0;
      }
      cout << "Odd" << endl;
    
  }

  
  return 0;
}
0