Zrobiłem to zadanie korzystając jedynie z chińskiego twierdzenia o resztach, rozwiązując układ maksymalnie 13 kongruencji, ale do tego potrzebne mi było trafianie za pomocą x+y w liczby pierwsze, co niestety wymagało około 450-500 zapytań dla x bliskich 10^14. Dużo za dużo. Co i tak nie zmienia faktu, że zabawa z tym była świetna :)
Z opisu przedstawionego w "solutions.pdf" widzę, że właściwym jest odgadywanie bitu po bicie. Jednak nie potrafię zrozumieć tego rozwiązania. Czy ktoś mógłby to prościej wytłumaczyć, a już najlepiej za pomocą przykładu?

Ja mam tak:

Obserwacja: jeżeli x=2^k mod 2^(k+1) to d(x) jest podzielne przez k+1.

Żeby zacząć pytamy sobie o d(x),d(x+1),...,d(x+7) któreś x+i jest 4mod8, więc d(x+i) podzielne przez 3. Ale może być takich i kilka. No to tworze liste kandydatów np niech 3|d(x+3) i 3|d(x+5). To sprawdzamy dalej d(x+3+8) i d(x+5+8). Któraś jest podzielna przez 3. Jak obie to dalej i dalej. Tylko to się szybko wykruszy. I zostanie jeden kandydat. Wtedy znamy x mod 8. I potem analogicznie wyznaczamy kolejne bity. Lepiej to robić po dwa bity naraz bo d(n) rzadko jest podzielne przez małe liczby nieparzyste, przez duże zresztą też.