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