s*********n
发帖数: 191 | 1 给定N个整数：
N1,N2,...,Nn.
和一个整数K.
只允许对每一个Ni的值进行增加，如果用最少的总增加值，使得这N个整数两两之间最
大公约数为K？
比如N={1 2 3} K=1这时增值就是0，因为123两两之间最大公约数本身就是1.
但是如N={2 2} K=1这时增值最小为1，因为2和(2+1)的最大公约数满足1.
如何解？ |
c*******2
发帖数: 60 | |
s*********n
发帖数: 191 | 3 dui
【在 c*******2 的大作中提到】
: Hacker Cup?
|
y*****g
发帖数: 10 | 4 假设N1-Nn有序。其实就是找最小n1,n2,n3,n4...的一个序列，n1*k >= N1, n2*k >=
N2...
将n1-nn处理成仅有1一个公约数的数列即可。 |
w*****t
发帖数: 485 | |
s*********n
发帖数: 191 | 6 不需要，先直接筛出一组素数，然后乘上K，双序列从前往后扫描。
是线性解。
已经AC了。
不需要DP贪心什么的。
【在 w*****t 的大作中提到】
: 要用dp做
: 用贪心fail了
|
f*******4
发帖数: 64 | 7 不一定非要素数*k
你是怎么知道AC的
【在 s*********n 的大作中提到】
: 不需要，先直接筛出一组素数，然后乘上K，双序列从前往后扫描。
: 是线性解。
: 已经AC了。
: 不需要DP贪心什么的。
|
s*********n
发帖数: 191 | 8 Hacker cup round 1
【在 f*******4 的大作中提到】
: 不一定非要素数*k
: 你是怎么知道AC的
|
c*******2
发帖数: 60 | 9 不一定都是素数的, 比如6 8对应的解应该是7 8.
不过不知道lz说的双序列扫描具体怎么操作, 是不是挑素数p_i >= a_i ? |
