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
- n ≤ 10^12
- m ≤ 2·10^5
Subtaskuri
| # | Punctaj | Restricţii |
|---|---|---|
| 1 | 7 | N ≤ 100 |
| 2 | 14 | N ≤ 2 000 |
| 3 | 28 | Xi, Yi ≤ 2 000 pentru orice 1 ≤ i ≤ N |
| 4 | 51 | 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
...
