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 in Bucuresti, pentru a isi indeplini odata pentru totdeauna telul.

Cerinta

Pentru un şir de numere a, definim costul ca 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) ca 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). Cum aceste numere pot fi foarte mari, Jupanul va roaga sa le afisati 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

Pe 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 respecta 1 ≤ i ≤ m

Subtaskuri

• Subtask Esti un om norocos, Gavrilescule! - 12 puncte: n ≤ 5 000, m ≤ 80 000, k_i ≤ 100 000
• Subtask Cata luciditate atata drama - 10 puncte: n ≤ 100 000, m ≤ 80 000, k_i ≤ 100 000
• Subtask Da-mi zilele inapoi - 11 puncte: n ≤ 1 000 000, m ≤ 80 000, k_i ≤ 100 000
• Subtask Aici ar trebui sa intre doar AIB - 24 puncte: m ≤ 500, k_i ≤ 200 000
• Subtask Du-te, dar nu mă vei uita - 42 puncte: m ≤ 80 000, k_i ≤ 200 000
• Subtask Si vesnicia chiar in dar s-o primim - 1 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?