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

h1. 'Soluţia':jc2023/solutii/jupanul problemei 'Salutare Jupâne':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$.

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