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 | 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
...