結果

問題 No.1113 二つの整数 / Two Integers
コンテスト
ユーザー どらら
提出日時 2020-07-17 21:42:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,596 bytes
コンパイル時間 1,678 ms
コンパイル使用メモリ 181,776 KB
実行使用メモリ 13,640 KB
最終ジャッジ日時 2024-11-29 22:49:22
合計ジャッジ時間 12,864 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 WA * 2 TLE * 5
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'ull PollardRho(ull, ull)':
main.cpp:32:22: warning: 'y' may be used uninitialized [-Wmaybe-uninitialized]
   32 |     p = gcd(n,llabs(x-y));
      |                     ~^~
main.cpp:24:9: note: 'y' was declared here
   24 |   ull x,y,p;
      |         ^
In function 'ull PollardRho(ull, ull)',
    inlined from 'std::vector<long long unsigned int> solvePollardRho(ull)' at main.cpp:41:19:
main.cpp:32:22: warning: 'y' may be used uninitialized [-Wmaybe-uninitialized]
   32 |     p = gcd(n,llabs(x-y));
      |                     ~^~
main.cpp: In function 'std::vector<long long unsigned int> solvePollardRho(ull)':
main.cpp:24:9: note: 'y' was declared here
   24 |   ull x,y,p;
      |         ^

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

typedef unsigned long long ull;
ull gcd(ull a, ull b){ return b==0?a:gcd(b,a%b); }
ull mulMod(ull a, ull b, ull mod){
  ull res = 0;
  a %= mod;
  while(b){
    if(b&1) res = (res+a)%mod;
    a = (a*2ULL)%mod;
    b = b/2ULL;
  }
  return res;
}
ull PollardRho(ull n, ull c=1){
  if(c>10) return -1ULL;
  ull x,y,p;
  x = p = 1ULL;
  int next=2, i=1;
  while(p==1){
    ++i;
    if(i==next){ y=x; next*= 2; }
    x = (mulMod(x,x,n)+c)%n;
    if(y==x) return PollardRho(n,c+1);
    p = gcd(n,llabs(x-y));
  }
  return p;
}
vector<ull> solvePollardRho(ull n){
  vector<ull> ret;
  ull r;
  while(true){
    if(n==1) break;
    r = PollardRho(n);
    if(r==-1ULL){ ret.push_back(n); sort(ret.begin(), ret.end()); return ret; }
    ret.push_back(r);
    n = n/r;
  }
  sort(ret.begin(), ret.end());
  return ret;
}


int main(){
  ull A, B;
  cin >> A >> B;

  vector<ull> x = solvePollardRho(A);
  vector<ull> y = solvePollardRho(B);

  map<ull,int> cntA, cntB, cnt;
  rep(i,x.size()){
    cntA[x[i]]++;
    cnt[x[i]] = 1;
  }
  rep(i,y.size()){
    cntB[y[i]]++;
    cnt[y[i]] = 1;
  }

  ull ans = 1;
  FOR(it,cnt){
    ull val = it->first;
    ull mn = min(cntA[val], cntB[val]);

    ans *= (mn+1);
  }

  if(ans % 2 == 0) cout << "Even" << endl;
  else cout << "Odd" << endl;
  
  return 0;
}
0