数次幂，3的倍数

Question

我们有号码 N 和费用 C，（范围 N<10^18 ,C<100）现在我们必须花费最多 C 卢比才能将数字转换为另一个数字。

数字转换规则如下：

1)一个数字可以转换为其他位数相同且没有前导零的数字。 2）将一个数字转换为其他数字的成本是相应数字的绝对差之和。例如，将 235 转换为 331 的成本为 5（因为相应数字的绝对差为 |3−2|+|3−3|+|1−5|，即 |1|+0+|−4| =5。现在我们需要找出在最大预算（C 卢比）内可以制作多少个 3 的倍数。

我的做法：我首先尝试使用 3 的整除规则并找到 N 的数字总和现在如果成本只是数字差的总和那么我们可以简单地做就是使总和成为 3 的倍数比如 2+3+5 = 10 成本是 2 我们可以将它设为 12，这可以通过将任何数字 2 、 3 或 5 增加 2 来实现 435,255, 237 这是正确的吗？在这种情况下，当 c 是绝对和

时，如何解决它

Answer 1

令 cost(a,b) 表示将 a 转换为 b 的成本并定义

 N(a,c) = # { b | cost(a,b) = c }

即，N(a,c) 是 a 的成本正好是 c 的数字的数量.

再假设_a_is能被3整除，那么我们感兴趣的数是：

 answer = N(a,0) + N(a,3) + N(a,6) + N(a,9) + ... + N(a,99)

如果 a 是 1 mod 3 我们需要总和 N(a,2) + N(a,5) + 。 .. + N(a,98).

为a中的每个数字d计算N(a,c) , 构建多项式 P(d) 其中 x^k 的系数是 [0..9] 中的位数，正好是 k 远离 d。这些系数将始终为 0、1 或 2。

例如，对于 a = 3496，多项式为：

  d   1  x  x^2 x^3 x^4 x^5 x^6 x^7 x^8 x^9
 -- --- --- --- --- --- --- --- --- --- ---   
  3   1   2   2   1   1   1   1   0   0   0
  4   1   2   2   2   2   1   0   0   0   0
  9   1   1   1   1   1   1   1   1   1   1
  6   1   2   2   2   1   1   1   0   0   0

N.B.: 数字3的x^3的系数是 1 而不是 2，因为不允许使用前导零。

现在将多项式相乘，N(a,c) 是 x^c 的系数在生成的产品中。

数次幂，3的倍数

Number Power , multiple of 3

math

logic

aptitude