結果
問題 |
No.1632 Sorting Integers (GCD of M)
|
ユーザー |
![]() |
提出日時 | 2021-07-30 22:05:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,605 bytes |
コンパイル時間 | 3,873 ms |
コンパイル使用メモリ | 229,756 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-16 00:20:10 |
合計ジャッジ時間 | 5,324 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 43 WA * 16 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll=long long; using Graph=vector<vector<pair<int,int>>>; #define MAX 100000 #define MOD 1000000007 #define INF 1000000000 int gcd(int a,int b){ while(a%b!=0){ int tmp=a%b; a=b; b=tmp; } return b; } ll modpow(ll a,ll n){ a%=MOD; ll ret=1; while(n>0){ if((n&1)==1){ ret=ret*a%MOD; } n>>=1; a=a*a%MOD; } return ret; } ll modinv(ll x){ return modpow(x,MOD-2); } int main(){ int N; cin>>N; vector<int> c(9); for(int i=0;i<9;i++){ cin>>c[i]; } bool even=true; if(N<=5){ vector<int> a; for(int i=0;i<9;i++){ for(int j=0;j<c[i];j++){ a.push_back(i+1); } } vector<int> nums; do{ int x=0; int res=1; for(int i=0;i<N;i++){ x+=a[i]*res; res*=10; } nums.push_back(x); }while(next_permutation(a.begin(),a.end())); int g=nums[0]; for(auto x:nums){ g=gcd(x,g); } cout<<g<<endl; return 0; } ll sum=0; int cnt=0; for(int i=0;i<9;i++){ sum+=((ll)i+1)*(ll)c[i]; if(c[i]>0){ cnt++; if(i%2==0){ even=false; } } } if(cnt!=1){ int ans=1; if(sum%9==0){ ans=9; }else if(sum%3==0){ ans=3; }else{ ans=1; } if(even==true){ ans*=2; } cout<<ans<<endl; }else{ int k=0; for(int i=0;i<9;i++){ if(c[i]>0){ k=i+1; } } ll x=(modpow(10,N)-1)*modinv(9)%MOD; x*=(ll)k; x%=MOD; cout<<x<<endl; } }