Codeforces #432 Div2 D

时间:2022-09-06 10:39:48

#432 Div2 D

题意

给出一些数字,如果这些数字的的 \(gcd\) 不为1则称这些数字 \(good\)。

可以有两种操作:

  1. 花费 x 删掉一个数
  2. 花费 y 将一个数加 1

问使这些数 \(good\) 的最小花费。

分析

一直找不到这题的重点。其实仔细想想与 \(gcd\) 有关,或者说与一个数列所有数的 \(gcd\) 有关,应该考虑到枚举所有的因子(或素因子),枚举因子对于求一系列数的 \(gcd\) 时貌似是很常见的。

对于本题,考虑枚举所有的素因子,设某个素因子为 \(p\),对于 \((j, j + p]\) \((j=k*p,k \in \mathbb{Z},k \geq 0)\) 这个区间,考虑这个区间的哪些数应该被删掉,哪些数应该增加至 \(j+p\)。

设 \(d\) 表示区间内某数与区间右端点的差值,如果 \(d*y>x\) ,那么应该删去。

有 \(d=\left \lceil \frac{x}{y} \right \rceil\),那么区间 \((j, j + p - d]\)里的数应该被删去,\((j+p-d, j + p]\)里的数增加至 \(j+p\)。

可以通过预处理出的前缀和以及数字出现次数的前缀和来高效的计算出答案。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 10;
int a[MAXN];
ll s[MAXN], sum[MAXN];
int notprime[MAXN];
vector<int> prime; int main() {
ios::sync_with_stdio(0);
cin.tie(0);
for(int i = 2; i < MAXN; i++) if(!notprime[i]) {
prime.push_back(i);
for(ll j = 1LL * i * i; j < MAXN; j += i) notprime[j] = 1;
}
int n, x, y;
cin >> n >> x >> y;
for(int i = 0; i < n; i++) {
cin >> a[i];
s[a[i]]++;
}
for(int i = 1; i < MAXN; i++) {
sum[i] = sum[i - 1] + s[i] * i;
s[i] += s[i - 1];
}
ll ans = 1e18;
int d = ceil(1.0 * x / y);
for(int p : prime) {
ll res = 0;
for(int j = 0; j < MAXN; j += p) {
if(p <= d) {
res += ((s[min(MAXN - 1, j + p)] - s[j]) * (j + p) - (sum[min(MAXN - 1, j + p)] - sum[j])) * y;
} else {
res += (s[min(MAXN - 1, j + p - d)] - s[j]) * x;
if(j + p - d + 1 > MAXN) break;
res += ((s[min(MAXN - 1, j + p)] - s[j + p - d]) * (j + p) - (sum[min(MAXN - 1, j + p)] - sum[j + p - d])) * y;
}
}
ans = min(ans, res);
}
cout << ans << endl;
return 0;
}

Codeforces #432 Div2 D的更多相关文章

  1. Codeforces &num;180 div2 C Parity Game

    // Codeforces #180 div2 C Parity Game // // 这个问题的意思被摄物体没有解释 // // 这个主题是如此的狠一点(对我来说,),不多说了这 // // 解决问 ...

  2. Codeforces &num;541 &lpar;Div2&rpar; - E&period; String Multiplication(动态规划)

    Problem   Codeforces #541 (Div2) - E. String Multiplication Time Limit: 2000 mSec Problem Descriptio ...

  3. Codeforces &num;541 &lpar;Div2&rpar; - F&period; Asya And Kittens(并查集&plus;链表)

    Problem   Codeforces #541 (Div2) - F. Asya And Kittens Time Limit: 2000 mSec Problem Description Inp ...

  4. Codeforces &num;541 &lpar;Div2&rpar; - D&period; Gourmet choice(拓扑排序&plus;并查集)

    Problem   Codeforces #541 (Div2) - D. Gourmet choice Time Limit: 2000 mSec Problem Description Input ...

  5. Codeforces &num;548 &lpar;Div2&rpar; - D&period;Steps to One(概率dp&plus;数论)

    Problem   Codeforces #548 (Div2) - D.Steps to One Time Limit: 2000 mSec Problem Description Input Th ...

  6. 【Codeforces &num;312 div2 A】Lala Land and Apple Trees

    # [Codeforces #312 div2 A]Lala Land and Apple Trees 首先,此题的大意是在一条坐标轴上,有\(n\)个点,每个点的权值为\(a_{i}\),第一次从原 ...

  7. codeforces round&num;432 div2

    C:这道题没做出来...写了个类似极角排序的东西被卡掉了...事实上暴力就行了,因为如果在二维平面内那么最多只能有4个点,因为每个象限只能有一个点,然后这里拓展一下就是最多只能有2*k个点,k是维数, ...

  8. Codeforces &num;263 div2 解题报告

    比赛链接:http://codeforces.com/contest/462 这次比赛的时候,刚刚注冊的时候非常想好好的做一下,可是网上喝了个小酒之后.也就迷迷糊糊地看了题目,做了几题.一觉醒来发现r ...

  9. codeforces &num;round363 div2&period;C-Vacations &lpar;DP&rpar;

    题目链接:http://codeforces.com/contest/699/problem/C dp[i][j]表示第i天做事情j所得到最小的假期,j=0,1,2. #include<bits ...

随机推荐

  1. 总结shell

    总结shell里面一些初学者不容易懂得点,因为我本身就是初学者,所以有一些知识点是不容易通过字面意思理解的,下面写在这里. (便于理解的一个方法就是举例子)举个例子就是哪些容易学,哪些不容易理解:丁是 ...

  2. &lbrack;译&rsqb;git pull

    git pull把git fetch和git merge压缩成了一条命令. 用法 git pull <remote> 作用和git fetch <remote> &&a ...

  3. MongoDB的学习和使用&lpar;固定集合&lbrack;Capped Collections&rsqb;&rpar;

    MongoDB 固定集合(Capped Collections) MongoDB 固定集合(Capped Collections)是性能出色且有着固定大小的集合,对于大小固定,我们可以想象其就像一个环 ...

  4. 降噪自动编码器(Denoising Autoencoder&rpar;

    起源:PCA.特征提取.... 随着一些奇怪的高维数据出现,比如图像.语音,传统的统计学-机器学习方法遇到了前所未有的挑战. 数据维度过高,数据单调,噪声分布广,传统方法的“数值游戏”很难奏效.数据挖 ...

  5. 关于用phonegap&plus;jquery moblie开发 白屏闪屏的解决方法

    前几天自己玩开发android应用,做些页面切换效果时,发现两个页面间切换间有白色闪屏的问题. 在网上找了很久的资料,还是没有解决. 最终,发现同事开发的android应用没有这个问题.对比代码排除发 ...

  6. 用github pages展示你的静态网页,多项目支持

    我看到有分享用github pages来做博客的,不过我并不想挂博客在上面,我只是想将我的一些作品挂上去,然后链接到我的简历里,这样HR可以直接看到. 首先是最基本的操作,在github上创建一个新的 ...

  7. nav

    $(document).ready(function() { $(window).resize(function(){ var need=0; var ul_max_width = $(window) ...

  8. Java---IO加强&lpar;1&rpar;

    RandomAccessFile ★随机访问文件,自身具备读写的方法. new RandomAccessFile()之后,若文件不存在会自动创建,存在则不创建.--该类其实内部既封装了字节输入流,又封 ...

  9. ClickOnce部署疑难杂症&colon;更新时部署与应用程序标识不一致问题。要安装此应用程序,请修改此文件的清单版本或卸载之前存在的应用程序。

    使用ClickOnce部署winform应用程序.无论是安装或者自动更新都极为方便,但有时候一些疑难杂症也令人头疼 1.注意每次部署完成之后 setup.exe无需覆盖,只需要在Application ...

  10. java中基本数据类型和C语言中基本数据类型转换

    java中 1 short = 2 byte 1 char  = 2 byte 1 int    = 4 byte 1 long = 8 byte C语言中 typedef unsigned char ...