結果
問題 |
No.1632 Sorting Integers (GCD of M)
|
ユーザー |
![]() |
提出日時 | 2021-07-30 22:03:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,489 bytes |
コンパイル時間 | 3,801 ms |
コンパイル使用メモリ | 229,920 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-16 00:16:15 |
合計ジャッジ時間 | 5,487 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 34 WA * 25 |
ソースコード
#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]; } 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(cnt!=1){ if(sum%9==0){ cout<<9<<endl; }else if(sum%3==0){ cout<<3<<endl; }else{ cout<<1<<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; } }