結果
問題 | 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; | ^
ソースコード
#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; }