結果
問題 |
No.443 GCD of Permutation
|
ユーザー |
![]() |
提出日時 | 2018-09-20 11:40:54 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 1,000 ms |
コード長 | 900 bytes |
コンパイル時間 | 1,017 ms |
コンパイル使用メモリ | 78,320 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-14 00:08:10 |
合計ジャッジ時間 | 1,840 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 28 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> using namespace std; typedef long long int ll; typedef pair<int, int> P; int gcd(int a, int b){ if(b==0) return a; return gcd(b, a%b); } int main() { string n; cin>>n; int d=n.size(); if(d==1){ cout<<n<<endl; return 0; } int g=-1; for(int i=d-1; i>=1; i--){ if(n[i]!=n[i-1]){ if(g==-1){ g=abs((int)(n[i]-n[i-1])); }else{ g=gcd(g, abs((int)(n[i]-n[i-1]))); } } } if(g==-1){ cout<<n<<endl; return 0; } g*=9; for(int k=g; k>=2; k--){ if(g%k!=0) continue; int r=0, p10=1; for(int i=d-1; i>=0; i--){ r+=((n[i]-'0')*p10%k); r%=k; p10*=10; p10%=k; } if(r==0){ cout<<k<<endl; return 0; } } cout<<1<<endl; return 0; }