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_JUDGE
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#endif
init_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 << "
";
return 0;
}