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 |
|---|---|
| 6 2 | 6 16 |
| 12152 8 | 12152 27468 57294 111704 207030 369846 642894 1093344 |
Explicaţie
Numarul 6 se descompune in 2 termeni astfel:
- [1,6], cost=gcd(1) + gcd([1,6])=1+1=2
- [6,1], cost=gcd(6) + gcd([6,1])=6+1=7
- [2,3], cost=gcd(2) + gcd([2,3])=2+1=3
- [3,2], cost=gcd(3) + gcd([3,2])=3+1=4
Deci f(6,2)=2+7+3+4=16
