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.