CF1305F Kuroni and the Punishment

題意：

給定 n 個數。每次可以選擇將一個數 +1 或 -1 。求至少多少次操作使得整個序列都是正數且全部元素的 gcd>1 。
$n<=2e5,a_i<=10^{12}$

題解：

首先不難想到，我們可以讓所有數變成偶數，這樣gcd為2，這樣的話，每個數的操作次數小于等于1，這是答案的上界n，也就是最后的答案只會比n優，不可能比n劣
由上面這個結論我可以推出一個定理：在最終的方案中，指定存在至少一半的元素，他們最多被操作過一次
證明：如果存在一般元素被操作了超過一次，那么操作次數就是$?\frac{n+1}{2}??2>n$,這超過了答案上界
所以，如果我們隨機選任意元素，這個元素至少有$\frac{1}{2}$的概率被最多操作一次。對于數x最多操作一次，可以得到x-1，x，x+1,也就是x最終有這個三個形態。因為gcd要>=2,說明x-1/x/x+1的某個因子就是我們要找的答案，那我們直接因子分解，對于每個因子w去強行判斷如果w是gcd所需要的操作次數，然后取min
為什么這樣是對的？
我們剛才說了，操作次數小于等于1的概率是>=$\frac{1}{2}$的，所以我們隨機選取k次，那么錯誤的概率就是$\frac{1}{2^k}$
當k>=30時一般不會出錯
還有隨機不要用rand()，詳細原因詳見如何正確地生成一個隨機數

代碼：

#include<bits/stdc++.h> using namespace std; mt19937 rnd(chrono::system_clock::now().time_since_epoch().count()); typedef long long ll; ll a[200005]; int n; ll cal(ll x) {ll ret=0;for (int i=0;i<n;i++){ll tmp=a[i]%x;if (a[i]!=tmp)ret+=min(tmp,x-tmp);elseret+=x-tmp;}return ret; }ll fac(ll x) {ll ret=1e18;ll en=sqrt(x+1ll);for(ll i=2;i<=en;i++){if (x%i==0){ret=min(ret,cal(i));while(x%i==0)x/=i;if (x==1)break;}}if (x>1)ret=min(ret,cal(x));return ret; } int main() { srand(time(0));cin>>n;for(int i=0;i<n;i++)scanf("%I64d",&a[i]);int T=50;ll ans=1e18;while (T--){ll pos=rnd()%n;if (a[pos]>2)ans=min(ans,fac(a[pos]-1ll));ans=min(ans,fac(a[pos]));ans=min(ans,fac(a[pos]+1ll));}cout<<ans; }

總結

以上是生活随笔為你收集整理的CF1305F Kuroni and the Punishment的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。