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

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.

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