g*********e
发帖数: 14401 | 1 you are given positive INTEGERS x1,x2,...xn and K. A valid solution is
comprised of INTEGER coefficients c1,c2,...cn>=0 and c>=1, so that
c*K=c1*x1+...+cn*xn.
Pls find a solution that minimizes c.
请教咋做 | b******n
发帖数: 4509 | 2 c = min(lcm(K, x_i))/K
lcm = least common multiple, i = 1...n
【在 g*********e 的大作中提到】
: you are given positive INTEGERS x1,x2,...xn and K. A valid solution is
: comprised of INTEGER coefficients c1,c2,...cn>=0 and c>=1, so that
: c*K=c1*x1+...+cn*xn.
: Pls find a solution that minimizes c.
: 请教咋做
| g*********e
发帖数: 14401 | 3
but the coeeficients ci could be 0 here...
【在 b******n 的大作中提到】
: c = min(lcm(K, x_i))/K
: lcm = least common multiple, i = 1...n
| b******n
发帖数: 4509 | 4 that's why there is min()
【在 g*********e 的大作中提到】
:
: but the coeeficients ci could be 0 here...
| j*******r
发帖数: 20 | 5 反例 x1=6 x2=9 K=15
【在 b******n 的大作中提到】
: c = min(lcm(K, x_i))/K
: lcm = least common multiple, i = 1...n
| g*********e
发帖数: 14401 | 6 i'm thinking of
c*K=sigma((ci+1)*xi)-sigma(xi)
so that we can apply the LCM thing, but couldn't figure out how to deal with
sigma(xi) | r****o
发帖数: 1950 | 7 I am thinking about using solution for coin problem.
x1, x2, ...xn are coins with different value, and each coin has unlimited
amount.
try
c*K=c1*x1+...+cn*xn. c increases from 1, 2, ...
until we find a solution.
【在 g*********e 的大作中提到】
: you are given positive INTEGERS x1,x2,...xn and K. A valid solution is
: comprised of INTEGER coefficients c1,c2,...cn>=0 and c>=1, so that
: c*K=c1*x1+...+cn*xn.
: Pls find a solution that minimizes c.
: 请教咋做
|
|
