Solutia problemei Salutare Jupane

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₁,a₂,...,a_t) pentru toate descompunerile lui n.

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.

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₁ + b₂ + ... + b_k = e, deci vom folosi stars and bars.

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.

Solutie in O(m·log²)

Vom schimba modul in care calculam raspunsul pentru un prefix. Sa presupunem ca n=p₁^e₁·p₂^e₂·...·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.