计算数字总和等于x * m的数字总和的数字x的编号

我试图解决以下问题，但是卡住了。我认为这是一个动态编程问题。你能否提出一些想法？计算数字总和等于x * m的数字总和的数字x的编号

问题：

给定一个正数N（N = < 18）和一个正数m个（m < = 100）。呼叫S（x）是x的数字之和。例如S（123）= 6 计数具有n个数字和S（x）= S（X * M）整数x的数

实施例：

n = 1时，m = 2的结果= 2

N = 18，m = 1个的结果= 1000000000000000000和

预先感谢。

来源

2015-09-14 nighthei

我不明白的问题。我似乎并不健康。在你的第一个例子中：x = 2，S（x）= S（2）= 2; S（x * m）= S（4）= 4，这违反了S（x）= S（x * m）。在第二种情况下，当m = 1时，任何具有n个数字的数字都是解决方案。 – isanco

如果DP在这里工作，我会感到非常惊讶。你为什么认为它会在这里工作？首先，我会寻找一些规则/模式。例如，9的可分性取决于（m模9），您可以自动限制可能的值。当然，如果m = 1,10,100，那么答案是显而易见的。 m = k * 10的答案与m = k的答案相同。仍然对于n = 18，在宇宙结束之前我看不出有什么办法解决这个问题。 –

@isanco。结果是2，因为'[0，9]'是可能的答案。 –

首先，我们需要拿出一个递推公式：

从最低显著位（LSD）开始到最显著数字（MSD），我们有一个有效的解决方案，如果以后我们计算MSD，我们有S(x) = S(x*m)

为了验证号码是否是一个有效的解决方案，我们需要知道三两件事：

什么是数字S（X）的电流和
什么是当前的总和数字S（x * m）
什么是当前数字。

因此，要回答的第一个和最后一个，很简单，我们只需要保持两个参数sum和digit。要计算第二个参数，我们需要维护两个附加参数sumOfProduct和lastRemaining。

sumOfProduct是当前S（X * M）
lastRemaining是(m * current digit value + lastRemaining)/10

例如，因此，我们有x = 123和m = 23

第一位数字= 3

sum = 3 
digit = 0 
sumOfProduct += (lastRemaining + 3*m) % 10 = 9 
lastRemaining = (m*3 + 0)/10 = 6

第二位数字= 2

sum = 5 
digit = 1 
sumOfProduct += (lastRemaining + 2*m) % 10 = 11 
lastRemaining = (m*2 + lastRemaining)/10 = 5

最后位= 1

sum = 6 
digit = 2 
sumOfProduct += (lastRemaining + m) % 10 = 19 
lastRemaining = (m + lastRemaining)/10 = 2

由于这是最后一个数字，sumOfProduct += S(lastRemaining) = 21。

所以，x = 123和m = 23是不是一个有效的数字。检查x*m = 2829 -> S(x*m) = S(2829) = 21。

所以，我们可以有一个递归公式(digit, sum, sumOfProdut, lastRemaining)。因此，我们的动态编程状态是dp[18][18*9 + 1][18*9 + 1][200]（因为m < = 100，所以lastRemaining不大于200）。

现在dp状态是300 MB，但是如果我们使用迭代的方法，这将变得更小，使用30MB左右

来源

2015-09-14 18:07:27

这个问题可以直接计算。

从这些文件：1，2和3（感谢@LouisRicci寻找他们），我们可以声明：

总和的倍数的数位的重复周期开始于最后重复（对于基-10 9）的数字，但一个从基数目
S(x)可以被定义为：让a等于x mod 9，如果a为零，结果为9，否则取a。 可以在下面的代码段ES6发挥它：

IN.oninput= (_=> OUT.value= (IN.value % 9) || 9); 
 
IN.oninput();

Input x:<br> 
 
<input id=IN value=123><br> 
 

 
S(x):<br> 
 
<input id=OUT disabled>

乘法规则：S(x * y) = S(S(x) * S(y))。

S(x)和S(x*m)对于x=0将始终为真，这样就不会有零结果。

考虑到上面的语句，我们应该calc下倍数的数位之和的重复周期为S(m)：

int m = 88; 
int Sm = S(m); // 7 

int true_n_times_in_nine = 0; 
for (int i=1; i<=9; i++) { 
    true_n_times_in_nine += i == S(i * Sm); 
}

答案则：

result = ((pow(10, n)/9) * true_n_times_in_nine);

加上一个因为案例零：

result++;

这里是一个ES6的解决方案：

S= x=> (x % 9) || 9; 
 
TrueIn9= (m, Sm=S(m))=> [1,2,3,4,5,6,7,8,9].filter(i=> i==S(i*Sm)).length; 
 
F= (n,m)=> ~~(eval('1e'+n)/9) * TrueIn9(m) + 1; 
 

 

 
N.oninput= 
 
M.oninput= 
 
f=(_=> OUT.value= F(N.value | 0, M.value | 0)); 
 
f();

Input n: (number of digits)<br> 
 
<input id=N value=1><br> 
 

 
Input m: (multiplicative number)<br> 
 
<input id=M value=2><br> 
 

 
F(n,m):<br> 
 
<input id=OUT disabled><br>

来源

2017-06-08 21:29:59

计算数字总和等于x * m的数字总和的数字x的编号

回答

相关问题