Tutaj masz dokładnie omówione jak znaleźć ile punktów o całkowitych współrzędnych jest w kole o zadanym promieniu, czyli zasadniczo to czego szukasz, przy czym w grę wchodzi m. in. rozkładanie liczb zespolonych na czynniki, ale rozwiązanie eleganckie
Dodano po 16 godzinach 18 minutach 33 sekundach:
A tak w skrócie jeśli nie chce ci się oglądać całego wykładu to dla koła o środku w początku układu współrzędnych i o promieniu
\(\displaystyle{ n}\) sprawdzasz po kolei okręgi o promieniach
\(\displaystyle{ 1,\sqrt{2}, \sqrt{3}, \ldots \sqrt{n^2}}\) i sprawdzasz przez ile punktów o całkowitych współrzędnych i nie będę się tu rozpisywał dlaczego tak jest, ale dla okręgu o promieniu
\(\displaystyle{ \sqrt{k}}\) rozkładasz
\(\displaystyle{ k}\) na czynniki pierwsze i:
-jeśli jest jakikolwiek czynnik pierwszy o 1 mniejszy od wielokrotności 4 (np. 3, 11) to musi być w parzystej potędze, każdy taki w nieparzystej automatycznie powoduje, że na tym okręgu nie ma punktów o całkowitych współrzędnych
-czynnik 2 w dowolnej potędze niczego nie zmienia
-każdy czynnik postaci o 1 większy niż wielokrotność 4 daje liczbę punktów o 1 większą niż jego potęga
-uzyskane tak punkty mnożysz przez 4
przykładowo okrąg o promieniu
\(\displaystyle{ \sqrt{25}}\) przecina 12 takich punktów, bo
\(\displaystyle{ 25 = 5^2}\) więc mamy czynnik o 1 większy od wielokrotności 4 w potędze 2, więc on daje 3 punkty, mnożymy przez 4, okrąg o promieniu
\(\displaystyle{ \sqrt{450}}\) da dokładnie tyle samo, bo
\(\displaystyle{ 450 = 2 \cdot 3^2 \cdot 5^2}\), dwójka nic nie zmienia, 3 jest w parzystej potędze, ale już okrąg o promieniu 150 nie przetnie żadnych punktów bo 3 będzie w nieparzystej
i tą metodą po kolei sumując punkty z kolejnych okręgów dostaniesz dokładny wynik