Frumos este ca surprizele pregatite de aceasta problema nu se termina aici. Putem obtine un algoritm si mai eficient, care sa obtina scorul de $100$ de puncte, daca mai facem o observatie. Formula $(*)$ sugereaza ca exista o sansa sa aflam valorea lui <tex> \chi(k) </tex> fara sa fie nevoie sa calculam valorile <tex> \chi(d) </tex>. Sa analizam, mai exact, care este factorul, notat cu $f()$, cu care trebuie adunat <tex> \Upsilon_{\Theta}(d) </tex> la raspuns, pentru fiecare $d$. De exemplu, daca $k = 2 * 3 * 5$ sa zicem, putem vedea ca <tex> f(\Upsilon_{\Theta}(2 * 3 * 5)) = 1 </tex>, <tex> f(\Upsilon_{\Theta}(2 * 3)) = f(\Upsilon_{\Theta}(2 * 5)) = f(\Upsilon_{\Theta}(3 * 5)) = -1 </tex>, <tex> f(\Upsilon_{\Theta}(2)) = f(\Upsilon_{\Theta}(3)) = f(\Upsilon_{\Theta}(5)) = 1 </tex>, respectiv <tex> f(\Upsilon_{\Theta}(1)) = -1 </tex>. Acest fenomen se generalizeaza in felul urmator:

* Fie $k = p{~1~}^a{~1~}^ * p{~2~}^a{~2~}^ * ... * p{~r~}^a{~r~}^$, descompunerea in factori primi a lui $k$
* <tex> f(\Upsilon_{\Theta}(d = p_1^{b_1} p_2^{b_2} \ldots p_r^{b_r})) = \{ (-1)^{\sum a_i - \sum b_i} </tex>, orice $d$ pentru care, oricare ar fi $i$, fie $b{~i~} = a{~i~}$, fie $b{~i~} = a{~i~} - 1$

* Fie $k = p{~0~}^a{~0~}^ * p{~1~}^a{~1~}^ * ... * p{~r-1~}^a{~r-1~}^$, descompunerea in factori primi a lui $k$
* <tex> f(\Upsilon_{\Theta}(d = p_0^{b_0} p_1^{b_1} \ldots p_{r-1}^{b_{r-1}})) = (-1)^{\sum a_i - \sum b_i} </tex>, orice $d$ pentru care, oricare ar fi $i$, fie $b{~i~} = a{~i~}$, fie $b{~i~} = a{~i~} - 1$
* <tex> f(\Upsilon_{\Theta}(d = p_0^{b_0} p_1^{b_1} \ldots p_{r-1}^{b_{r-1}})) = 0 </tex>, orice $d$ pentru care exista $i$ astfel incat $b{~i~} &le; a{~i~} - 2$
 
Aceste observatii contureaza algoritmul pe care il vom implementa. Atunci cand e nevoie sa aflam valoarea lui <tex> \chi(k) </tex>, il descompunem pe $k$ in factori primi si, prin backtracking sau nu, pentru fiecare numar $mask$ intre $0$ si $2^r^ - 1$ vom obtine divizorul pentru care $b{~i~} = a{~i~} - bool(2^i^ `and` mask)$ si vom aduna la rapuns <tex> (-1)^{popcount(mask)} \Upsilon_{\Theta}(d) </tex>. In acest fel, nu mai e nevoie nici de recursivitate, nici de memoizare, nici de ciur, deoarece putem afla pe loc (in urma unei descompuneri in factori primi si a $2^r^$ ridicari la putere in timp logaritmic) valorile cautate.