* Sunt multe feluri de a imbunatati solutia precedenta: Putem precalcula puterile lui <tex> \Sigma </tex>, il putem cauta pe $T$ in <tex> O(log(n)) </tex> sau in <tex> O(1) </tex>, amortizat sau nu. Putem gasi divizorii unui numar cu un algoritm mai eficient, sau putem chiar folosi ciur pentru a determina valorile din sirul $s$.
* Pasul important catre solutia de $100$ de puncte il constituie observatia ca numarul de numere mai mari ale caror valori in sirul $s$ sunt interesante pentru noi este foarte scazut, si putem folosi memoizare pentru calculul acestora. O observatie care poate fi de folos aici e ca $T$ divide $2n$, prin urmare putem incerca divizorii sai, pentru care cautam valori $K, A$ pentru care exista o sansa sa se potriveasca in ecuatie, iar apoi calculam valorile relevante din $s$ pentru a actualiza raspunsul. Pentru un punctaj mai mare, putem calcula prin ciur valorile necesare pana la o anumita valoare, $10.000$ sa zicem, si doar pentru celelalte memoizam.

Se cade sa facem un scurt rezumat al aventurii noastre cu aceasta problema. Am facut observatii legate de relatia intre forma sirului de caractere si numarul de perechi de chei care nu pot fi distinse. Am analizat aspecte ale numararii sirurilor neperiodice, sub incidenta proprietatilor care ne intereseaza. Am fost uimiti sa vedem cum toate se leaga, valorile pe care voiam sa le calculam se foloseau, in chip neasteptat, de ele insele, inlesnind drumul de la recurenta la solutie. Mai mult, am fost surprinsi sa vedem cat de mult se simplifica operatiile, ajungand sa retinem intr-un sir de numere tot ce ne-ar putea interesa. Apoi am cautat solutii eficiente de a implementa solutia, folosindu-ne de forma ecuatiei care leaga parametrii de numarul din input. A fost un tur de forta care ne-a trecut prin multe observatii, multe idei ad-hoc, si am ajuns, intr-un final, la un algoritm simplu, eficient, sprijinit pe multimea observatiilor facute, care exploateaza _materie_ relativ redusa si tehnici deloc complicate.

Se cade sa facem un scurt rezumat al aventurii noastre cu aceasta problema. Am facut observatii legate de relatia intre forma sirului de caractere si numarul de perechi de chei care nu pot fi distinse. Am analizat aspecte ale numararii sirurilor neperiodice, sub incidenta proprietatilor care ne intereseaza. Am fost uimiti sa vedem cum toate se leaga, valorile pe care voiam sa le calculam se foloseau, in chip neasteptat, de ele insele, inlesnind drumul de la recurenta la solutie. Mai mult, am fost surprinsi sa vedem cat de mult se simplifica operatiile, ajungand sa retinem intr-un sir de numere tot ce ne-ar putea interesa. Apoi am cautat solutii eficiente de a implementa solutia, folosindu-ne de forma ecuatiei care leaga parametrii de numarul din input. A fost un tur de forta care ne-a trecut prin multe observatii, multe idei ad-hoc, si am ajuns, intr-un final, la un algoritm simplu, eficient, sprijinit pe multimea observatiilor facute, care exploateaza _materie_ relativ redusa si tehnici deloc complicate (valabil si pentru solutia de mai jos).

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: