Salutare Jupâne

Salutare Jupane

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

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.

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$.

h2. Cerinţă

Definim $f(n,k)$ ca fiind suma costurilor tuturor partitiilor lui $n$ in $k$ termeni‡.

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$.

Dandu-se $n$ si $m$, voi trebuie sa calculati $f(n,1), f(n,2),...,f(n,m)$

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{~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 partitie a lui $n$ in $k$ termeni, intelegem un sir de numere pozitive $a{~1~},a{~2~},...a{~k~}$ cu proprietatea ca $a{~1~}·a{~2~}·...·a{~k~}=n$

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

Pe prima si singura linie a fisierului $jupanul.in$ contine numerele $n$ si $m$ separate printr-un spatiu.

h2. 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{~1~}), f(n, k{~2~}),..., f(n, k{~m~})$ separate prin exact un spaţiu.

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.

h2. Restricţii

* $1 ≤ n ≤ 10^12^$
* $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

* $n ≤ 10^12$
* $m ≤ 2·10^5$

h2. Subtaskuri

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

table(restrictii). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $7$ | $N ≤ 100$ |
| $2$ | $14$ | $N ≤ 2 000$ |
| $3$ | $28$ | $X{~i~}, Y{~i~} ≤ 2 000$ pentru orice $1 ≤ i ≤ N$ |
| $4$ | $51$ | Fără restricţii suplimentare |

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

| 6 2
  1 2
| 6 16

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

| 12152 8
  1 2 3 4 5 6 7 8
| 12152 27468 57294 111704 207030 369846 642894 1093344
|
 

h3. Explicaţie

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

...

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