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(%{color:black}$[1$%$]$) + gcd([1,6])=1+1=2
• [6,1], cost=gcd(%{color:black}$[6$%$]$) + gcd([6,1])=6+1=7
• [2,3], cost=gcd(%{color:black}$[2$%$]$) + gcd([2,3])=2+1=3
• [3,2], cost=gcd(%{color:black}$[3$%$]$) + gcd([3,2])=3+1=4

Deci f(6,2)=2+7+3+4=16

Cum se trimit solutii?