結果
問題 | No.443 GCD of Permutation |
ユーザー |
![]() |
提出日時 | 2016-11-11 23:18:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,141 bytes |
コンパイル時間 | 790 ms |
コンパイル使用メモリ | 87,076 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-25 10:41:59 |
合計ジャッジ時間 | 1,736 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 22 WA * 6 |
ソースコード
#include<iostream> #include<vector> #include<string> #include<cstring> #include<algorithm> #include<map> #include<set> #include<cmath> #include<cassert> #include<queue> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef vector<int> vi; int main() { string N; cin >> N; int n = N.size(); sort(N.begin(), N.end()); if (n <= 8) { int ans = 0; do { ans = __gcd(ans, stoi(N)); } while (next_permutation(N.begin(), N.end())); cout << ans << endl; return 0; } if (N[0] == N[n-1]) { cout << N << endl; return 0; } if (N[n-2] == '0') { cout << N[n-1] << endl; return 0; } int sum = 0; int cnt0 = 0, cnt2 = 0, cnt4 = 0, cnt8 = 0; for (char c : N) { int num = c-'0'; sum += num; if (num == 0) ++cnt0; else { if (num%2 == 0) ++cnt2; if (num%4 == 0) ++cnt4; if (num%8 == 0) ++cnt8; } } int ans = 1; if (sum%9 == 0) ans *= 9; else if (sum%3 == 0) ans *= 3; if (cnt8 > 0 && cnt8 + cnt0 == n) ans *= 8; else if (cnt4 > 0 && cnt4 + cnt0 == n) ans *= 4; else if (cnt2 > 0 && cnt2 + cnt0 == n) ans *= 2; cout << ans << endl; return 0; }