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

I-a luat Jupânului 4652 de zile să cureţe Londra de mafioţi. I-a ramas doar unul, anume burghezul metabalzacian Stănică Raţiu. De aceea Jupanul a venit in Bucuresti, pentru a isi indeplini odata pentru totdeauna telul.

Cerinta

Pentru un şir de numere a, definim costul că fiind suma gcdurilor† tututor prefixelor lui a. De exemplu, costul şirului [12, 6, 9, 2] este gcd(12) + gcd(12, 6) + gcd(12, 6, 9) + gcd(12, 6, 9, 2) = 12 + 6 + 3 + 1 = 22.

Definim f(n,k) că fiind suma costurilor tuturor partitiilor lui n în k termeni‡.

Dându-se n şi m, si un sir k₁, k₂, ..., k_m, voi trebuie să calculaţi f(n, k₁), f(n, k₂),..., f(n, k_m)

† Prin gcd(a₁, a₂,..., a_i) s-a notat cel mai mare divizor comun al numerelor a₁, a₂,..., a_i.
‡ Prin o partiţie a lui n în k termeni, înţelegem un şir de numere pozitive a₁, a₂,..., a_k cu proprietatea că a₁ · a₂· ... · a_k=n

Date de intrare

Pe prima şi singură linie a fişierului jupanul.în conţine numerele n şi m separate printr-un spaţiu.

Date de ieşire

Pe prima şi singură linie a fişierului jupanul.out se vor află f(n, k₁), f(n, k₂),..., f(n, k_m) separate prin exact un spaţiu.

Restricţii

• 1 ≤ n ≤ 10¹²
• 1 ≤ m ≤ 200 000
• 1 ≤ k_i ≤ 200 000, pentru orice i care respecta 1 ≤ i ≤ m

Subtaskuri

• Subtask Componente Biconexe - 9 puncte: n ≤ 5 000
• Subtask Componente Triconexe - 6 puncte: n ≤ 100 000
• Subtask Componente Tare Conexe - 8 puncte: n ≤ 1 000 000
• Subtask Cuplaj - 7 puncte: m ≤ 5
• Subtask Flux - 37 puncte: m ≤ 1 500
• Subtask Intersectie de Meteoriti - 33 puncte: Fără restricţii suplimentare

Exemplu

Explicaţie

Numărul 6 se descompune în 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?