結果
問題 |
No.443 GCD of Permutation
|
ユーザー |
![]() |
提出日時 | 2025-01-27 18:10:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 60 ms / 1,000 ms |
コード長 | 943 bytes |
コンパイル時間 | 2,331 ms |
コンパイル使用メモリ | 197,788 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2025-01-27 18:10:16 |
合計ジャッジ時間 | 4,026 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 28 |
コンパイルメッセージ
main.cpp: In function ‘void AC::solve()’: main.cpp:24:31: warning: ‘void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<char*, __cxx11::basic_string<char> >]’ is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations] 24 | random_shuffle(all(s)); | ~~~~~~~~~~~~~~^~~~~~~~ In file included from /usr/include/c++/13/algorithm:61, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51, from main.cpp:1: /usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here 4581 | random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last) | ^~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h> #define int long long #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() using namespace std; template<typename T>istream&operator>>(istream&I,vector<T>&v){for(auto&i:v)I>>i;return I;} template<typename T>ostream&operator<<(ostream&O,vector<T>&v){for(auto&i:v)O<<i<<' ';return O;} namespace AC{ void solve(){ string s; cin>>s; int n=s.size(); vector<bool>vis(10); for(auto i:s)vis[i-'0']=1; int d=0; for(int i=0;i<10;i++)for(int j=i+1;j<10;j++)if(vis[i]&&vis[j])d=__gcd(d,9*(j-i)); if(!d){ cout<<s<<endl; return; } vector<bool>ans(100); for(int i=1;i<100;i++)if(d%i==0)ans[i]=1; for(int i=0;i<50;i++){ random_shuffle(all(s)); for(int j=1;j<100;j++)if(ans[j]){ int tmp=0; for(int k=0;k<n;k++)tmp=(tmp*10+s[k]-'0')%j; if(tmp^0)ans[j]=0; } } for(int i=99;i>=0;i--)if(ans[i]){ cout<<i<<endl; return; } } } signed main(){ int t=1; //cin>>t; while(t--)AC::solve(); }