結果
問題 | No.937 Ultra Sword |
ユーザー |
![]() |
提出日時 | 2019-11-29 22:26:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 56 ms / 3,000 ms |
コード長 | 1,379 bytes |
コンパイル時間 | 1,157 ms |
コンパイル使用メモリ | 110,804 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-21 02:23:16 |
合計ジャッジ時間 | 3,391 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
コンパイルメッセージ
main.cpp: In function 'int gcd(int, int)': main.cpp:44:19: warning: 'ib' may be used uninitialized [-Wmaybe-uninitialized] 44 | b^=(a<<(ib-ia)); | ~~~^~~~ main.cpp:31:17: note: 'ib' was declared here 31 | int ia, ib; | ^~ main.cpp:44:19: warning: 'ia' may be used uninitialized [-Wmaybe-uninitialized] 44 | b^=(a<<(ib-ia)); | ~~~^~~~ main.cpp:31:13: note: 'ia' was declared here 31 | int ia, ib; | ^~
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; int gcd(int a, int b){ if(a>b) swap(a, b); if(a==0) return b; int ia, ib; for(int i=16; i>=0; i--){ if(a&(1<<i)){ ia=i; break; } } for(int i=16; i>=0; i--){ if(b&(1<<i)){ ib=i; break; } } b^=(a<<(ib-ia)); return gcd(a, b); } int main() { int n; cin>>n; int c[100010]={}; int a[100010]; for(int i=0; i<n; i++){ cin>>a[i]; c[a[i]]++; } int g=a[0]; for(int i=1; i<n; i++){ g=gcd(g, a[i]); } int ig=0; for(int i=16; i>=0; i--){ if(g&(1<<i)){ ig=i; break; } } ll ans=0; for(int i=0; i<n; i++) ans+=a[i]; ll sum0=ans; for(int d=1; d<=100000; d++){ int x=d; for(int i=16; i>=ig; i--){ if(x&(1<<i)){ x^=(g<<(i-ig)); } } if(x) continue; ll sum=sum0; for(int i=d; i<=100000; i+=d){ sum-=(ll)c[i]*(i-i/d); } ans=min(ans, sum); } cout<<ans<<endl; return 0; }