Contare il numero del numero x che ha la somma delle cifre uguale alla somma delle cifre di x * m

Question

Stavo cercando di risolvere il seguente problema, ma sono bloccato. Penso che sia un problema di programmazione dinamica. Potrebbe per favore dare qualche idea?

Problema:

Dato un numero positivo n (n = < 18) e un numero positivo m (m < = 100). Chiamata S (x) è la somma delle cifre di x. Ad esempio S (123) = 6 contare il numero di numero intero x che ha n cifre e S (x) = S (x * m)

Esempio:

n = 1, m = 2 risultato = 2

n = 18, m = 1 risultato = 1000000000000000000

Grazie in anticipo.

Answer 1

In primo luogo, abbiamo bisogno di trovare una formula ricorsiva:

A partire dalla cifra meno significativa (LSD) per la cifra più significativa (MSD), abbiamo una soluzione valida se dopo calcoliamo la MSD, abbiamo S(x) = S(x*m)

per verificare se un numero è una valida soluzione, abbiamo bisogno di sapere tre cose:

• Qual è la somma corrente di cifre S (x)
• Qual è la corrente somma della cifra S (x * m)
• Qual è la cifra corrente.

Quindi, per rispondere per la prima e l'ultima, è facile, abbiamo solo bisogno di mantenere due parametri sum e digit. Per calcolare il secondo, è necessario mantenere due parametri aggiuntivi, sumOfProduct e lastRemaining.

• sumOfProduct è la corrente S (x * m)
• lastRemaining è il risultato di (m * current digit value + lastRemaining)/10

Ad esempio, abbiamo x = 123 e m = 23

• Prima cifra = 3

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

• Seconda cifra = 2

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

• Ultima cifra = 1

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

  Poiché questa è l'ultima cifra, sumOfProduct += S(lastRemaining) = 21.

Così, x = 123 e m = 23 non è un numero valido. Controllare x*m = 2829 -> S(x*m) = S(2829) = 21.

Quindi, possiamo avere una formula ricorsiva con stato (digit, sum, sumOfProdut, lastRemaining).

Pertanto, il nostro stato di programmazione dinamica è dp[18][18*9 + 1][18*9 + 1][200] (come m < = 100, quindi lastRemaining non superiore a 200).

Ora lo stato dp a più di 300 MB, ma se usiamo un approccio iterativo, diventerà più piccola, con circa 30 MB

Answer 2

Questo problema può essere calcolato direttamente.

Da tali documenti: 1, 2 e 3(grazie a @LouisRicci per trovare loro), possiamo affermare:

1. Il ciclo ripetitivo di somma delle cifre di multipli inizia a ripetere l'ultimo cifre, ma dalla base-numero (9 per la base-10)

2. S(x) possono essere definiti come: lasciate a uguale x mod 9, se a è zero, prendi 9 come risultato, altrimenti prendi a. Si può giocare nel frammento ES6 di seguito:

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>

3. Moltiplicazione regola: S(x * y) = S(S(x) * S(y)).

4. S(x) e S(x*m) saranno sempre veri per x=0, in questo modo non vi è alcun risultato zero.

---

Con le dichiarazioni di cui sopra in mente, dovremmo calc il ciclo ripetitivo di somma delle cifre di multipli per 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); 
} 

La risposta allora:

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

Più uno a causa del caso zero:

result++; 

Qui è una soluzione 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>