Salutare Jupane

Salutare Jupâne

== include(page="template/taskheader" task_id="jupanul") ==

I-a luat Jupanului 4652 de zile să cureţe Londra de mafioţi. Dar când şi-a terminat planul de răzbunare, a început să se simtă gol, lipsit de orice dorinţa de a îşi continuă viaţă de altfel monotonă. "Poate că defapt nu vrem să ne îndeplinim visurile", şi-a spus. Dar această apatie asurzitoare avea să se termine odată ce găseşte o poză ce se află în geacă unuia din uzurpatori. Această îi ilustra în mod clar pe Crawford Starrick dând mâna cu nimeni altul decât burghezul metabalzacian Stănică Raţiu. Asta i-a readus speranţa pentru viitor Jupanului, pentru că asta însemna că încă are un tel căruia se poate dedică. Aşa că şi-a făcut portbagajul şi a plecat îndată la Bucureşti.

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.

h2. Cerinta

h2. Cerinţă

Pentru un şir de numere $a$, definim _costul_ că fiind suma gcdurilor† tututor prefixelor lui $a$. De exemplu, costul şirului $[4, 4, 2, 1]$ este $gcd(4) + gcd(4, 4) + gcd(4, 4, 2) + gcd(4, 4, 2, 1) = 4 + 4 + 2 + 1 = 11$.

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)$ că fiind suma costurilor tuturor partitiilor lui $n$ în $k$ termeni‡.

Definim $f(n,k)$ ca fiind suma costurilor tuturor partiţiilor lui $n$ în $k$ termeni.{$‡$}

Dându-se $n$ şi $m$, voi trebuie să calculaţi $f(n, 1), f(n, 2),..., f(n, m)$

Dându-se $n$ şi $m$, şi un şir $k{~1~}, k{~2~}, ..., k{~m~}$, voi trebuie să calculaţi $f(n, k{~1~}), f(n, k{~2~}),..., 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{~1~}, a{~2~},..., a{~i~})$ s-a notat "cel mai mare divizor comun":https://en.wikipedia.org/wiki/Greatest_common_divisor al numerelor $a{~1~}, a{~2~},..., a{~i~}$.
‡ Prin o partiţie a lui $n$ în $k$ termeni, înţelegem un şir de numere pozitive $a{~1~}, a{~2~},..., a{~k~}$ cu proprietatea că $a{~1~} · a{~2~}· ... · a{~k~}=n$

$†$ Prin $gcd(a{~1~}, a{~2~},..., a{~i~})$ s-a notat "cel mai mare divizor comun":https://en.wikipedia.org/wiki/Greatest_common_divisor al numerelor $a{~1~}, a{~2~},..., a{~i~}$.
$‡$ Prin o partiţie a lui $n$ în $k$ termeni, înţelegem un şir de numere pozitive $a{~1~}, a{~2~},..., a{~k~}$ cu proprietatea că $a{~1~} · a{~2~}· ... · a{~k~}=n$

h2. Date de intrare

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

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{~1~}, k{~2~}, ..., k{~m~}$.

h2. Date de ieşire

Pe prima şi singură linie a fişierului $jupanul.out$ se vor află $f(n, 1), f(n, 2),..., f(n, m)$ separate prin exact un spaţiu.

Pe prima şi singura linie a fişierului $jupanul.out$ se vor afla resturile modulo $998244353$ ale numerelor $f(n, k{~1~}), f(n, k{~2~}),..., f(n, k{~m~})$ separate prin exact un spaţiu.

h2. Restricţii
* $1 ≤ n ≤ 10^12^$

* $1 ≤ m ≤ 2·10^5^$

* $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":https://www.infoarena.ro/parsare-fisier-intrare şi a "fişierelor de ieşire":https://www.infoarena.ro/parsare-fisier-iesire

h2. Subtaskuri

table(restrictii). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $9$ | $n ≤ 5 000$ |
| $2$ | $6$ | $n ≤ 100 000$ |
| $3$ | $8$ | $n ≤ 1 000 000$ |
| $4$ | $7$ | $m ≤ 5$ |
| $5$ | $39$ | $m ≤ 1 500$ |
| $6$ | $31$ | Fără restricţii suplimentare |

* $Subtask %{color:#55DDE0; font-weight:bold} Eşti un om norocos, Gavrilescule!% - 11 puncte (testele 1-2): n ≤ 5 000, m ≤ 80 000, k{~i~} ≤ 100 000$
* $Subtask %{color:#33658A; font-weight:bold} Câtă luciditate atâta dramă% - 12 puncte (testele 3-4): n ≤ 100 000, m ≤ 80 000,  k{~i~} ≤ 100 000$
* $Subtask %{color:#2F4858; font-weight:bold} Dă-mi nopţile înapoi% - 10 puncte (testele 5-6): n ≤ 1 000 000, m ≤ 80 000, k{~i~} ≤ 100 000$
* $Subtask %{color:#F6AE2D; font-weight:bold} Aici ar trebui să intre doar AIB% - 24 puncte (testele 7-10): m ≤ 500, k{~i~} ≤ 200 000$
* $Subtask %{color:#D62828; font-weight:bold} Du-te, dar nu mă vei uita% - 42 puncte (testele 11-15): m ≤ 80 000, k{~i~} ≤ 200 000$
* $Subtask %{color:#A82371; font-weight:bold} Şi veşnicia chiar în dar s-o primim% - 1 punct (testul 16): Fără restricţii suplimentare$

h2. Exemplu
table(example). |_. jupanul.in |_. jupanul.out |
| 6 2

  1 2

| 6 16
|
| 12152 8

  1 2 3 4 5 6 7 8

| 12152 27468 57294 111704 207030 369846 642894 1093344
|

* {$[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$

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

== include(page="template/taskfooter" task_id="jupanul") ==