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(a₁, a₂,..., a_i) s-a notat cel mai mare divizor comun al numerelor a₁, a₂,..., a_i.
‡ Prin o partitie a lui n in k termeni, intelegem un sir de numere pozitive a₁, a₂,..., a_k cu proprietatea ca a₁ · a₂· ... · a_k=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 ≤ 10¹²
• 1 ≤ m ≤ 2·10⁵

Subtaskuri

Exemplu

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

Cum se trimit solutii?