Policz liczbę x, która ma sumę cyfr równą sumie cyfr x * m

Question

Próbowałem rozwiązać następujący problem, ale utknąłem. Myślę, że jest to problem programowania dynamicznego. Czy możesz podać kilka pomysłów?

problemu:

względu dodatnią liczbę n (n < = 18) i liczbę dodatnią < m (m = 100). Wywołanie S (x) jest sumą cyfr x. Na przykład S (123) = 6 Policzyć liczba całkowita X, który ma N cyfr i S (X) = S (X * m)

przykład:

n = 1, m = 2 wynik = 2

n = 18, m = 1, wynik = 1000000000000000000

Dzięki wcześniej.

Answer 1

Po pierwsze, musimy wymyślić rekurencyjnego wzoru:

Zaczynając od najmniej znaczącej cyfry (LSD) do najbardziej znaczącej cyfry (MSD), mamy ważne rozwiązanie jeśli po obliczamy MSD, mamy S(x) = S(x*m)

aby sprawdzić, czy dana liczba jest ważne rozwiązanie, musimy wiedzieć trzy rzeczy:

• Jaki jest obecny suma cyfr S (x)
• Jaki jest obecny suma cyfr S (x * m)
• Jaka jest bieżąca cyfra.

Aby odpowiedzieć na pierwszy i na koniec, jest to łatwe, musimy jedynie zachować dwa parametry: sum i digit. Aby obliczyć drugi, musimy zachować dwa dodatkowe parametry, sumOfProduct i lastRemaining.

• sumOfProduct jest obecny S (X * m)
• lastRemaining jest wynikiem (m * current digit value + lastRemaining)/10

na przykład, mieć x = 123 i m = 23

• Pierwsza cyfra = 3

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

• Druga cyfra = 2

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

• Ostatnia cyfra = 1

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

  Ponieważ jest to ostatnia cyfra, sumOfProduct += S(lastRemaining) = 21.

Więc x = 123 i m = 23 nie jest prawidłowy numer. Sprawdź x*m = 2829 -> S(x*m) = S(2829) = 21.

Możemy więc mieć formułę rekurencyjną o stanie (digit, sum, sumOfProdut, lastRemaining).

W ten sposób nasz stan programowania dynamicznego to dp[18][18*9 + 1][18*9 + 1][200] (jako m < = 100, więc lastRemaining nie większy niż 200).

Teraz stan dp ma ponad 300 MB, ale jeśli używamy iteracyjnego podejścia, staje się mniejsze, stosując około 30MB

Answer 2

Problem ten można obliczyć bezpośrednio.

Z tych dokumentów: 1, 2 i 3(dzięki @LouisRicci dla ich znalezieniem), możemy podać:

1. cykl powtórzeń Suma cyfr wielokrotności zacznie powtarzać w ostatniej cyfrowy ale z bazy-Number (9 do 10) bazowego

2. S(x) można zdefiniować jako: niech a równe x mod 9 jeśli a to zero, weź jako wynik 9, a następnie pobierz a. Można grać we fragmencie ES6 poniżej:

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. mnożenie zasadę: S(x * y) = S(S(x) * S(y)).

4. S(x) i S(x*m) będzie zawsze prawdziwe dla x=0, w ten sposób nie będzie żadnego wyniku zerowego.

---

Z powyższych stwierdzeń na uwadze, powinniśmy calc cykl powtórzeń Suma cyfr wielokrotności dla 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); 
} 

Odpowiedź następnie:

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

Plus jeden z powodu zera:

result++; 

Oto rozwiązanie 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>