建设网站需要做app吗,陕西省网站备案,做谷歌推广一定要网站吗,做网址导航网站891 ModricWangs Number Theory II 思路 使得序列的最大公约数不为1#xff0c;就是大于等于2#xff0c;就是找到一个大于等于2的数#xff0c;它能够整除序列中的所有数。 考虑使得一个数d整除数组中所有数的代价#xff1a; 如果一个数不能被b整除#xff0c;那么可以花…891 ModricWangs 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)))\) 代码 #includeiostream
#includecstringusing 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;
} 转载于:https://www.cnblogs.com/AlvinZH/p/7761607.html
