h1. 'Solutia':jc2023/solutii/omida problemei 'Salutare Jupane':problema/jupanul
h1. 'Soluţia':jc2023/solutii/jupanul problemei 'Salutare Jupâne':problema/jupanul
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$.
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$.
h2. Solutie in $O(m·nrdiv·log)$
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$.
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$.
Sa fixam $x$, si sa numaram cate descompuneri ale lui $n$ au $k$ termeni si prefixul de lungime $t$ are gcdul multiplu de $x$. Putem face acest lucru pur si simplu numarand 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.
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.
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.
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.
h2. Solutie in $O(m·log^2^)$
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, acesta 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.
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.
