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?