891 ModricWang's Number Theory II
思路
使得序列的最大公約數不為1，就是大于等于2，就是找到一個大于等于2的數，它能夠整除序列中的所有數。
考慮使得一個數d整除數組中所有數的代價：
如果一個數不能被b整除，那么可以花費x的代價刪掉它，或者通過多次加1使得它可以被d整除，代價應該為 \((d - a[i]\%d) * y\) , \((a[i] \% d == 0s時特判，應該為0)\)
令 \(l = x / y\)
如果\(d - a[i] \% d <= l\) \((a[i]\%d != 0)\), 這個數產生的代價是 \((d - a[i] \% d) * y\) , 否則是\(x\)。
所有代價求和就是總代價，最小的總代價就是答案。
但是這樣枚舉了d和a[i], 復雜度是\(O(n^2)\) 的。
考慮將a[i]換一種方式存儲：b[i]表示值為i的數出現的次數。
這樣d可以將b分成如下若干段：
\([0, d - 1], [d, d * 2 - 1], [d * 2, d * 3 - 1], ... ,[d * i, d * (i + 1) - 1]\)
對于每一段而言，
\([d * (i + 1) - l, d * (i + 1) - 1]\) 內的數應該通過多次加1變成\(d * (i + 1)\) ,
代價應為 \((該區間內數的個數 * d * (i + 1) - 該區間內的數之和) * y\)
\([d * i + 1 , d * (i + 1) - l - 1]\) 內的數應該直接刪除,
代價應為 \(該區間內的個數 * x\)
通過構造相應的前綴和數組，上述操作均可以在\(O(1)\) 的時間復雜度內完成
具體操作時應該注意邊界
因為合數會被質數整除，因此d可以只枚舉質數。
計算時間復雜度需要一些數論知識。首先素數密度(也就是 \(\frac{小于n的素數}{n}\) )可以參見oeis A006880,一個近似解析式為 \(\frac{1}{ln(n)}\)，那么\(小于n的素數的總個數\)可以近似為 \(\frac{n}{ln(n)}\)
設小于等于n的素數為\(prime[i]\)，素數總數為\(P\),取近似\(P=\frac{n}{ln(n)}\)
求結果部分的復雜度可以寫為 \(\sum_{1}^{P} \frac{n}{prime[i]}\)
參見wikipedia,素數的倒數和又可以近似為 \(\sum_{1}^{p} \frac{1}{prime[i]}=ln(ln(n))\)
因此 \(\sum_{1}^{P} \frac{n}{prime[i]} = O(n* ln(ln(n)))\)
這里得到了計算結果部分的復雜度，還需要加上求素數這個過程的時間復雜度。如果使用樸素篩法，求復雜度的過程正好的上文所述的完全一致，其復雜度為\(O(n*ln(ln(n)))\)。如果使用歐拉篩求素數，復雜度為\(O(n)\)。
因此\(O(運行時間)=O(求素數)+O(計算結果)=O(n*ln(ln(n)))\)
代碼
#include<iostream>
#include<cstring>using namespace std;const long long Max_Ai = 1000000*2;
long long n, x, y, l;
long long nums[Max_Ai + 10];
long long s[Max_Ai + 10], sum[Max_Ai + 10];bool valid[Max_Ai + 10];
long long prime[Max_Ai + 10];
long long tot;//線性篩求素數
void init_prime() {memset(valid, true, sizeof(valid));for (int i = 2; i <= Max_Ai; i++) {if (valid[i]) prime[++tot] = i;for (int j = 1; j <= tot && i*prime[j] <= Max_Ai; j++) {valid[i*prime[j]] = false;if (i%prime[j]==0) break;}}
}int main() {
#ifdef ONLINE_JUDGEios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#endifinit_prime();cin >> n >> x >> y;l = x/y;for (long long i = 1; i <= n; i++) {long long p;cin >> p;nums[p]++; //這是一種比較特別的數字記錄方法，原理類似于基數排序radix sort}for (long long i = 1; i <= Max_Ai; i++) {s[i] = s[i - 1] + nums[i]; //數量和sum[i] = sum[i - 1] + nums[i]*i; //前綴和}auto min_cost = (long long) 1e18;for (long long i = 1; i <= tot; i++) {long long k = prime[i];long long now_cost = 0;for (long long j = 0; j <= Max_Ai; j += k) {long long mid = max(j + k - l - 1, j);long long bound = min(j + k - 1, Max_Ai);if (bound > mid) {now_cost += ((s[bound] - s[mid])*(j + k) - (sum[bound] - sum[mid]))*y;now_cost += (s[mid] - s[j])*x;} else {now_cost += (s[bound] - s[j])*x;}}min_cost = min(min_cost, now_cost);}cout << min_cost << "\n";return 0;
}
, 這部分都是angular)
