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 4653 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 în Bucuresti, pentru a-şi îndeplini odată pentru totdeauna ţelul.

Cerinţă

Pentru un şir de numere a, definim costul ca fiind suma gcd-urilor† 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) ca fiind suma costurilor tuturor partiţiilor lui n în k termeni.‡

Dându-se n şi m, şi un şir k₁, k₂, ..., k_m, voi trebuie să calculaţi f(n, k₁), f(n, k₂),..., f(n, k_m). Cum aceste numere pot fi foarte mari, Jupânul vă roagă să le afişaţi modulo 998244353.

† 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

Prima linie a fişierului jupanul.în conţine numerele n şi m separate printr-un spaţiu. Pe a doua linie, se vor afla m numere k₁, k₂, ..., k_m.

Date de ieşire

Pe prima şi singura linie a fişierului jupanul.out se vor afla resturile modulo 998244353 ale numerelor f(n, k₁), f(n, k₂),..., f(n, k_m) separate prin exact un spaţiu.

Restricţii

• 1 ≤ n ≤ 10¹²
• 1 ≤ m ≤ 1 500 000
• 1 ≤ k_i ≤ 1 500 000, pentru orice i care respectă 1 ≤ i ≤ m
• Din cauza dimensiunii mari a testelor, se recomandă parsarea fişierelor de intrare şi a fişierelor de ieşire

Subtaskuri

• Subtask Eşti un om norocos, Gavrilescule! - 11 puncte (testele 1-2): n ≤ 5 000, m ≤ 80 000, k_i ≤ 100 000
• Subtask Câtă luciditate atâta dramă - 12 puncte (testele 3-4): n ≤ 100 000, m ≤ 80 000, k_i ≤ 100 000
• Subtask Dă-mi nopţile înapoi - 10 puncte (testele 5-6): n ≤ 1 000 000, m ≤ 80 000, k_i ≤ 100 000
• Subtask Aici ar trebui să intre doar AIB - 24 puncte (testele 7-10): m ≤ 500, k_i ≤ 200 000
• Subtask Du-te, dar nu mă vei uita - 42 puncte (testele 11-15): m ≤ 80 000, k_i ≤ 200 000
• Subtask Şi veşnicia chiar în dar s-o primim - 1 punct (testul 16): 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?