計算數字總和等於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的編號

回答

相關問題