h1. 'Soluţia':jc2023/solutii/jupanul problemei 'Salutare Jupâne':problema/jupanul

h1. 'Solutia':jc2023/solutii/omida problemei 'Salutare Jupane':problema/jupanul

Vom încerca să tratăm suma independent pe fiecare prefix al descompunerii. Astfel, vom fixa prefixul de lungime $t$ şi vom calcula suma din gcd(a{1}, a{2}, ..., a{t}) pentru toate descompunerile lui $n$.

Vom incerca sa tratam suma independent pe fiecare prefix al descompunerii. Astfel vom fixa prefixul de lungime $t$ si vom calcula suma din gcd(a{~1~},a{~2~},...,a{~t~}) pentru toate descompunerile lui $n$.

h2. Solutie in $O(m·nrdiv·log)$

Este cunoscut că suma din $phi(i)$ pentru toţi divizorii lui $n$ este chiar $n$, unde $phi(i)$ reprezintă numărul de numere prime cu $i$ mai mici decât $i$. Astfel, în loc să calculăm suma din gcd, vom calcula suma din $phi(x)$ cu $x | gcd$.

Este cunoscut ca suma din $phi(i)$ pentru toti divizorii lui $n$ este chiar $n$, unde $phi(i)$ reprezinta numarul de numere prime cu $i$ mai mici decat $i$. Astfel in loc sa calculam suma din gcd, vom calcula suma din $phi(x)$ cu $x | gcd$.

Să fixăm $x$ şi să numărăm câte descompuneri ale lui $n$ au $k$ termeni şi prefixul de lungime $t$ are gcd-ul multiplu de $x$. Singura condiţie impusă este că primii $t$ termeni din descompunere să fie multipli de $x$, deci trebuie să numărăm descompunerile lui $n/x^t$ în $k$ termeni, lucru care poate fi făcut cu uşurinţă considerând fiecare factor prim independent şi înmulţind răspunsurile. Dacă un factor prim are exponent $e$, atunci avem nevoie de numărul de soluţii ale $b{1} + b{2} + ... + b{k} = e$, deci vom folosi "stars and bars":https://cp-algorithms.com/combinatorics/stars_and_bars.html.

Sa fixam $x$, si sa numaram cate descompuneri ale lui $n$ au $k$ termeni si prefixul de lungime $t$ are gcdul multiplu de $x$. Singura conditie inpusa este ca primii $t$ termeni din descompunere sa fie multipli de $x$, deci trebuie sa numaram descompunerile lui $n/x^t^$ in $k$ termeni, lucru care poate fi facut cu usurinta considerand fiecare factor prim independent si inmultind raspunsurile. Daca un factor prim are exponent $e$, atunci avem nevoie de numarul de solutii ale $b{~1~} + b{~2~} + ... + b{~k~} = e$, deci vom folosi "stars and bars":https://cp-algorithms.com/combinatorics/stars_and_bars.html.

Pentru a obţine complexitatea din subtitlu, folosim memoizare pentru a nu calcula descompunerile de mai multe ori decât este necesar şi observăm că pentru orice $x > 1$, acesta poate contribui doar în $log$ prefixe.

Pentru a obtine complexitatea din subtitlu, folosim memoizare pentru a nu calcula descompunerile de mai multe ori decat este necesar si observam ca pentru orice $x > 1$, acesta poate contribui doar in $log$ prefixe.

h2. Solutie in $O(m·log^2^)$

Vom schimba modul în care calculăm răspunsul pentru un prefix. Să presupunem că $n=p{~1~}^e{~1~}^·p{~2~}^e{~2~}^·...·p{~l~}^e{~l~}^$. Vom folosi $dp[i] = suma tuturor gcd-urilor considerând doar primii i factori primi$. Observăm că $dp[i] = dp[i-1]·(suma tuturor gcd-urilor când considerăm doar factorul prim curent)$, întrucât orice $gcd$ care poate fi obţinut doar cu factorul prim curent poate fi cuplat cu orice $gcd$ vechi, deci în final doar înmulţim răspunsurile pentru fiecare factor prim separat. Acum putem folosi soluţia de dinainte, doar că nu mai trebuie să considerăm toţi divizorii, ci doar cei care sunt puteri ale unui număr prim, în total $log$ astfel de numere.

Vom schimba modul in care calculam raspunsul pentru un prefix. Sa presupunem ca $n=p{~1~}^e{~1~}^·p{~2~}^e{~2~}^·...·p{~l~}^e{~l~}^$. Vom folosi $dp[i] = suma tututor gcdurilor considerand doar primii i factori primi$. Observam ca $dp[i] = dp[i-1]·(suma tuturor gcdurilor cand consideram doar factorul prim curent)$, intrucat orice $gcd$ care poate fi obtinut doar cu factorul prim curent poate fi cuplat cu orice $gcd$ vechi, deci in final doar inmultim raspunsurile pentru fiecare factor prim separat. Acum putem folosi solutia de dinainte, doar ca nu mai trebuie sa consideram toti divizorii, ci doar cei care sunt puteri ale unui numar prim, in total $log$ astfel de numere.