题目
给你n个正整数，你每次可以选择一个数加一或减一。 所有位置始终要为正整数。 请求出使得所有数的gcd不为1的最小操作次数。 N<=2e5 Ai<=1e12
思路
如果你假定gcd=d，只需要扫一遍就可以求出答案。 注意到，d=2时答案上界是n。 所以无论答案是什么，至少有一半的数至多被操作一次。 这引导我们搞一个不确定性的算法。 随机取一个ai，然后将ai,ai+1,ai-1的所有质因数试一次。求出答案的概率是50%。 多求几次即可
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std
;
const int N
=2e5+10;
int n
;
ll a
[N
];
set
<ll
> checked
,calced
;
ll
check(ll x
){
if(checked
.count(x
))return LLONG_MAX
;
checked
.insert(x
);
ll ans
=0;
for(int i
=1;i
<=n
;i
++)if(a
[i
]<=x
){
ans
+=x
-a
[i
];
}else{
ans
+= min(a
[i
]%x
,x
-a
[i
]%x
);
}
return ans
;
}
ll
calc(ll x
){
if(!x
||calced
.count(x
))return LLONG_MAX
;
calced
.insert(x
);
ll ans
=LLONG_MAX
;
for(ll i
=2;i
*i
<=x
;i
++)if(x
%i
==0){
ans
= min(ans
,check(i
));
while(x
%i
==0)x
/=i
;
}
if(x
!=1)ans
= min(ans
,check(x
));
return ans
;
}
int main(){
scanf("%d",&n
);
srand(time(NULL));
for(int i
=1;i
<=n
;i
++) scanf("%lld",&a
[i
]);
for(int i
=n
;i
>=1;i
--) swap(a
[i
],a
[rand()%i
+1]);
ll ans
=LLONG_MAX
;
for(int k
=1;k
<=n
&&clock()/(double)CLOCKS_PER_SEC
<.1;k
++){
ans
= min(ans
,calc(a
[k
]));
ans
= min(ans
,calc(a
[k
]+1));
ans
= min(ans
,calc(a
[k
]-1));
}
printf("%lld\n",ans
);
}
