#include<bits/stdc++.h>
using namespace std;
long long pas;
const int N=10000000;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[100009],msh[100009],zm[100009],cmp,K[100009],C,D,E,KK[100009];
pair <int, int> fx[10000009],fx2[10000009];
vector <pair <int, pair <int, int> > > P;
int fnd(int q){
if(msh[q]==0) return q; else return msh[q]=fnd(msh[q]);
}
void mrg(int q, int w){
q=fnd(q);w=fnd(w);
if(q==w) return;
pas+=e;cmp--;
if(zm[q]<zm[w]) swap(q,w);
msh[w]=q;
if(zm[q]==zm[w]) zm[q]++;
}
void updfx(int q, int w){
if(w==N+5) return;
if(fx[q].first==N+5){
fx[q].first=w;
}else{
if(fx[q].second==N+5){
if(fnd(fx[q].first)!=fnd(w)) fx[q].second=w;
}
}
}
void updfx2(int q, int w){
if(w==-1) return;
if(fx2[q].first==-1){
fx2[q].first=w;
}else{
if(fx2[q].second==-1){
if(fnd(fx2[q].first)!=fnd(w)) fx2[q].second=w;
}
}
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>a;map <int, int> ma;
zx=0;
for(i=1; i<=a; i++){
cin>>c;
if(ma[c]!=-1){
ma[c]=-1;
zx++;f[zx]=c;
}
}
a=zx;
if(a==1){
cout<<0;
return 0;
}
cmp=a;
while(cmp>1){
for(i=0; i<=N+3; i++){
fx[i]={N+5,N+5};fx2[i]={-1,-1};
if(i<=a+2){
K[i]=N+5;KK[i]=0;
}
}
for(i=1; i<=a; i++){
//c=fnd(i);
fx[f[i]]={i,N+5};
for(j=f[i]; j<=N; j+=f[i]){
fx2[j].second=fx2[j].first;
fx2[j].first=i;
}
}
for(i=N-1; i>=0; i--){
/*if(fx[i+1].first!=N+5){
if(fx[i].first==N+5){
fx[i].first=fx[i+1].first;
}else{
if(fx[i].second==N+5){
fx[i]
}
}
}*/
updfx(i,fx[i+1].first);
updfx(i,fx[i+1].second);
}
for(i=1; i<=N; i++){
updfx2(i,fx2[i-1].first);
updfx2(i,fx2[i-1].second);
}
i=2;
//cout<<f[i]<<" "<<fx2[f[i]].first<<" "<<fx2[f[i]].second<<"\n";
for(i=1; i<=a; i++){
C=fnd(i);
for(j=f[i]; j<=N; j+=f[i]){
ii=fx[j].first;
if(ii==N+5) continue;
D=fnd(ii);
if(D==C){
ii=fx[j].second;
if(ii==N+5) continue;
D=fnd(ii);
}
zx=f[ii]%f[i];
if(K[C]>zx){
K[C]=zx;KK[C]=D;
}
}
for(int ha=1; ha<=1; ha++){
//
ii=fx2[f[i]].first;
if(ii==-1) break;
D=fnd(ii);
if(D==C){
ii=fx2[f[i]].second;
if(ii==-1) break;
D=fnd(ii);
}
/*cout<<i<<" "<<ii<<" "<<f[i]<<" "<<f[ii]<<"\n";
return 0;*/
zx=f[i]%f[ii];
if(K[C]>zx){
K[C]=zx;KK[C]=D;
}
//
}
}
/*for(i=1; i<=a; i++){
cout<<K[i]<<" "<<KK[i]<<"\n";
}*/
for(i=1; i<=a; i++){
if(K[i]==N+5) continue;
c=i;d=KK[i];e=K[i];
mrg(c,d);
//
K[i]=N+5;
}
}
cout<<pas;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1147 ms |
156940 KB |
Output is correct |
| 2 |
Execution timed out |
5069 ms |
156944 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5084 ms |
156928 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1100 ms |
156948 KB |
Output is correct |
| 2 |
Correct |
610 ms |
156928 KB |
Output is correct |
| 3 |
Correct |
672 ms |
157024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5079 ms |
163104 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5064 ms |
157780 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5077 ms |
163060 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5070 ms |
159252 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5067 ms |
163480 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5049 ms |
163496 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5033 ms |
158300 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
