Czy jest jakaś szybka droga w C (poniżej 1 sekundy), aby znaleźć liczbę doskonałych kwadratów między dwiema liczbami. Na przykład dla 1 < -> 10 mamy 2 doskonałe kwadraty 4 i 9. Ale co pomiędzy 1 < -> 2^60 lub jakąś inną większą liczbą.Idealne kwadraty między dwiema liczbami
jest wolna
while(i*i<=n)
{
sum+=i==((long long)(sqrt(i*i)));
i++;
}
gdzie n jest powiedzmy 2^60 i początek i = 2.
To trywialne. Załóżmy, że masz dwa punkty końcowe: & b, z < b.
Jaki jest następny idealny kwadrat po? Podpowiedź, co to jest sqrt (a)? Co zrobi zaokrąglenie?
Jaki jest największy idealny kwadrat, który nie przekracza wartości b? Podpowiedź, co to jest sqrt (b)? Ponownie, jak tu zaokrąglić pomoc?
Gdy znasz już te dwie liczby, liczenie liczby doskonałych kwadratów wydaje się naprawdę banalne.
Przy okazji, bądź ostrożny. Nawet sqrt z 2^60 jest dużą liczbą, chociaż zmieści się w podwójnym. Problem polega na tym, że 2^60 jest zbyt duży, aby zmieścić się w standardowym podwójnym, ponieważ przekracza 2^53. Więc uważaj na problemy z precyzją.
+ dobra sztuczka, dzięki! –
if(n1 is a perfect square)
x=(int)sqrt(n2)-(int)sqrt(n1)+1;
else
x=(int)sqrt(n2)-(int)sqrt(n1);
Nie powtarzam. Równanie:
floor(sqrt(b)) - ceil(sqrt(a)) + 1
daje liczbę doskonałych pól w przedziale od a aż do b włącznie.
* poniżej 1 s * 1 sekundę na co, 486 lub GeForce 560? –
Dlaczego, 2^30 - 1? Czy możesz obliczyć 'sqrt' punktów końcowych i dowiedzieć się, ile liczb całkowitych znajduje się w tym zakresie? –