題目鏈接

https://codeforces.com/contest/1305/problem/F

題解

真的想不出……然而大家都會
考慮枚舉最終所有數的 \(\gcd\)，設為 \(g\). \(g=2\)時操作次數不超過 \(n\), 故答案不超過 \(n\).
對于 \(g>2\), 只有操作次數小于 \(n\) 時才有貢獻。那么考慮每個元素的操作次數，肯定存在至少一個元素的操作次數為 \(0\), 因此只需要枚舉那些至少是輸入中一個數的因數的數；又不難發現只需要枚舉質數。以上都是鋪墊，現在離正解只差一個Key observation.
觀察到絕大部分情況下操作次數都是 \(0\) 或 \(1\). 具體來講，至少有一半的數操作次數都不超過 \(1\). 于是每次隨機選序列中的一個數 \(x\)，檢驗 \(x-1,x,x+1\) 的所有質因子即可，設進行 \(T\) 輪，則正確率至少為 \((1-\frac{1}{2^T})\).
時間復雜度 \(O(T(\sqrt W+n))\)，其中 \(W=\max a_i\).

代碼

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define riterator reverse_iterator using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int N = 2e5; const int MX = 1e6; bool isp[MX+3]; int pri[MX+3]; llong a[N+3]; map<llong,int> done; int n,prin; llong ans;int randw() {return (rand()<<15)|rand();}void EulerSieve() {isp[1] = 1;for(int i=2; i<=MX; i++){if(!isp[i]) {pri[++prin] = i;}for(int j=1; j<=prin&&i*pri[j]<=MX; j++){isp[i*pri[j]] = 1;if(i%pri[j]==0) break;}} }void check(llong x) {if(done.count(x)) return; done[x] = 1;llong ret = 0ll;for(int i=1; i<=n; i++){ret += a[i]<x?x-a[i]%x:min(a[i]%x,x-a[i]%x);}ans = min(ans,ret); } void check1(llong x) {for(llong i=2; i*i<=x; i++){if(isp[i]) continue;if(x%i==0){check(i);while(x%i==0) {x/=i;}}}if(x>1) {check(x);} }int main() {srand(time(NULL));EulerSieve();scanf("%d",&n);for(int i=1; i<=n; i++) scanf("%lld",&a[i]);for(int i=1; i<=n; i++) {ans += a[i]&1;}for(int T=1; T<=20; T++){int i = randw()%n+1;check1(a[i]); check1(a[i]-1); check1(a[i]+1);}printf("%I64d\n",ans);return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

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

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