QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#89182 | #21. GCD-sum | Silver187 | 0 | 2ms | 3572kb | C++14 | 2.5kb | 2023-03-19 10:49:26 | 2023-03-19 10:49:30 |
Judging History
answer
#include <bits/stdc++.h>
#include <assert.h>
#include <unordered_set>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define LL long long
#define pp pair<int,int>
#define mp make_pair
#define ull unsigned long long
namespace IO{
const int sz=1<<22;
char a[sz+5],b[sz+5],*p1=a,*p2=a,*t=b,p[105];
inline char gc(){
return getchar();
// return p1==p2?(p2=(p1=a)+fread(a,1,sz,stdin),p1==p2?EOF:*p1++):*p1++;
}
template<class T> void gi(T& x){
x=0; int f=1;char c=gc();
if(c=='-')f=-1;
for(;c<'0'||c>'9';c=gc())if(c=='-')f=-1;
for(;c>='0'&&c<='9';c=gc())
x=x*10+(c-'0');
x=x*f;
}
inline void flush(){fwrite(b,1,t-b,stdout),t=b; }
inline void pc(char x){*t++=x; if(t-b==sz) flush(); }
template<class T> void pi(T x,char c='\n'){
if(x<0)pc('-'),x=-x;
if(x==0) pc('0'); int t=0;
for(;x;x/=10) p[++t]=x%10+'0';
for(;t;--t) pc(p[t]); pc(c);
}
struct F{~F(){flush();}}f;
}
using IO::gi;
using IO::pi;
using IO::pc;
using IO::gc;
const int mod=1e9+7;
const int inv2=(mod+1)>>1;
inline int add(int x,int y){
return x+y>=mod?x+y-mod:x+y;
}
inline int dec(int x,int y){
return x-y<0?x-y+mod:x-y;
}
inline int qkpow(int a,int b){
int ans=1,base=a;
while(b){
if(b&1)ans=1ll*ans*base%mod;
base=1ll*base*base%mod;
b>>=1;
}
return ans;
}
int fac[1000005],inv[1000005],Invn[1000005];
inline int binom(int n,int m){
if(n<m||m<0)return 0;
return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void init_C(int N){
fac[0]=1;
for(int i=1;i<=N;i++)fac[i]=1ll*fac[i-1]*i%mod;
inv[0]=1;
inv[N]=qkpow(fac[N],mod-2);
for(int i=N-1;i>=1;i--)inv[i]=1ll*inv[i+1]*(i+1)%mod;
Invn[0]=Invn[1]=1;
for(int i=2;i<=N;i++)Invn[i]=1ll*inv[i]*fac[i-1]%mod;
}
int n,len;
LL a[500005],b[1234];
__int128 ans[500005],sum;
gp_hash_table<LL,int>H;
bool vis[500005];
signed main(){
gi(n);
LL d=0;
for(int i=1;i<=n;i++)gi(a[i]),sum+=a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
LL tmp=d;
d=__gcd(d,a[i]);
if(d!=tmp)b[++len]=d;
}
H[a[1]]=1;
for(int i=2;i<=n;i++){
if(H[a[i]])vis[i]=1;
else H[a[i]]=1;
}
ans[0]=sum;
for(int i=1;i<=len;i++){
LL d=b[i];
__int128 sum2=sum-a[1]+d;
int now=0;
for(int j=2;j<=n;j++){
if(vis[j]||a[j]%d==0){
now++;
sum2-=a[j];
ans[now]=max(ans[now],sum2);
}
}
}
for(int i=n-1;i>=0;i--)pi(ans[i],' ');
return 0;
}
/*
*/
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3416kb
input:
7 18 30 10 23 1 3 13
output:
1 31 54 72 85 95 98
result:
wrong answer 1st lines differ - expected: '1', found: '1 31 54 72 85 95 98 '
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #31:
score: 0
Wrong Answer
time: 0ms
memory: 3412kb
input:
100 268 467 21 173 158 287 36 446 36 340 311 283 58 77 464 119 460 198 405 331 214 331 255 157 418 319 354 289 330 64 11 484 186 129 130 368 370 468 292 180 427 76 87 156 13 379 268 170 3 15 263 52 296 242 7 296 376 148 221 270 218 131 326 198 399 132 270 55 299 444 134 222 278 486 409 72 38 193 359...
output:
1 497 990 1476 1960 2428 2895 3359 3819 4274 4720 5164 5591 6009 6420 6829 7234 7633 8028 8422 8801 9177 9547 9915 10277 10636 10990 11335 11675 12006 12337 12667 12993 13312 13623 13934 14244 14543 14839 15135 15427 15716 16003 16286 16564 16838 17108 17378 17646 17914 18181 18444 18699 18941 19166...
result:
wrong answer 1st lines differ - expected: '1', found: '1 497 990 1476 1960 2428 2895 ... 24505 24518 24529 24536 24540 '
Subtask #4:
score: 0
Wrong Answer
Test #51:
score: 0
Wrong Answer
time: 2ms
memory: 3572kb
input:
1270 1 2 6 7 8 9 10 11 13 14 16 18 19 20 22 23 25 26 28 30 31 32 33 37 38 40 42 43 44 45 46 47 48 49 50 52 53 55 56 57 58 59 62 63 64 67 68 69 70 71 72 74 75 77 78 80 85 86 87 88 89 90 92 96 97 98 99 100 101 103 104 105 107 108 109 113 119 122 124 126 128 132 134 135 137 140 143 144 149 150 151 154 ...
output:
1 1996 3990 5983 7975 9966 11955 13943 15928 17912 19895 21873 23849 25824 27796 29767 31737 33706 35674 37641 39607 41570 43531 45490 47447 49402 51354 53304 55251 57197 59142 61084 63024 64963 66900 68836 70770 72703 74632 76560 78487 80413 82337 84260 86182 88103 90023 91941 93856 95770 97683 995...
result:
wrong answer 1st lines differ - expected: '1', found: '1 1996 3990 5983 7975 9966 119...269987 1269994 1270000 1270002 '
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #4:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
0%