Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | jupanul.in, jupanul.out | Sursă | Junior Challenge 2023 |
| Autor | Cozma Tiberiu Stefan | Adăugată de |  Voicu Mihai Valeriu •cadmium_ |
| Timp execuţie pe test | 4 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Salutare Jupâne
Pentru un sir de numere a, definim costul ca fiind suma gcdurilor† tututor prefixelor lui a. De exemplu, costul sirului [4,4,2,1] este gcd(4) + gcd(4,4) + gcd(4,4,2) + gcd(4,4,2,1) = 4+4+2+1 = 11.
Definim f(n,k) ca fiind suma costurilor tuturor partitiilor lui n in k termeni‡.
Dandu-se n si m, voi trebuie sa calculati f(n,1), f(n,2),...,f(n,m)
† Prin gcd(a1,a2,...,ai) s-a notat cel mai mare divizor comun al numerelor a1,a2,...,ai.
‡ Prin o partitie a lui n in k termeni, intelegem un sir de numere pozitive a1,a2,...ak cu proprietatea ca a1·a2·...·ak=n
Date de intrare
Pe prima si singura linie a fisierului jupanul.in contine numerele n si m separate printr-un spatiu.
Date de ieşire
Pe prima si singura linie a fisierului jupanul.out se vor afla f(n,1), f(n,2),...,f(n,m) separate prin exact un spatiu.
Restricţii
- 1 ≤ n ≤ 1012
- 1 ≤ m ≤ 2·105
Subtaskuri
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 10 | n ≤ 5000 |
| 2 | 20 | n ≤ 100000 |
| 3 | 10 | m ≤ 5 |
| 4 | 10 | n este o putere a unui numar prim |
| 5 | 50 | Fără restricţii suplimentare |
Exemplu
| jupanul.in | jupanul.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
