Soluţia problemei Salutare Jupâne

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.

Solutie in O(m·nrdiv·log)

Este cunoscut că suma din phi(i) pentru toţi divizorii lui n este chiar n, unde phi(i) reprezintă numărul de numere prime cu i mai mici decât i. Astfel, în loc să calculăm suma din gcd, vom calcula suma din phi(x) cu x | gcd.

Să fixăm x şi să numărăm câte descompuneri ale lui n au k termeni şi prefixul de lungime t are gcd-ul multiplu de x. Singura condiţie impusă este că primii t termeni din descompunere să fie multipli de x, deci trebuie să numărăm descompunerile lui n/x^t în k termeni, lucru care poate fi făcut cu uşurinţă considerând fiecare factor prim independent şi înmulţind răspunsurile. Dacă un factor prim are exponent e, atunci avem nevoie de numărul de soluţii ale b{1} + b{2} + ... + b{k} = e, deci vom folosi stars and bars.

Pentru a obţine complexitatea din subtitlu, folosim memoizare pentru a nu calcula descompunerile de mai multe ori decât este necesar şi observăm că pentru orice x > 1, acesta poate contribui doar în log prefixe.

Solutie in O(m·log²)

Vom schimba modul în care calculăm răspunsul pentru un prefix. Să presupunem că n=p₁^e₁·p₂^e₂·...·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.