Có cách nào nhanh chóng trong C (dưới 1 giây) để tìm số ô vuông hoàn hảo giữa hai số. Ví dụ: cho 1 < -> 10 chúng tôi có 2 ô vuông hoàn hảo 4 và 9. Nhưng khoảng giữa 1 < -> 2^60 hoặc một số số lớn hơn khác.Hình vuông hoàn hảo giữa hai số
Đây là chậm
while(i*i<=n)
{
sum+=i==((long long)(sqrt(i*i)));
i++;
}
trong đó n là cho phép nói 2^60 và chúng tôi bắt đầu với i = 2.
tầm thường của nó. Giả sử bạn có hai điểm cuối, & b, với < b.
Hình vuông hoàn hảo tiếp theo sau là gì? Gợi ý, sqrt là gì (a)? Điều gì sẽ làm tròn lên?
Hình vuông hoàn hảo lớn nhất nào không vượt quá b? Gợi ý, sqrt (b) là gì? Một lần nữa, làm thế nào sẽ làm tròn giúp đỡ ở đây?
Một khi bạn biết hai số, đếm số ô vuông hoàn hảo có vẻ thực sự tầm thường.
Nhân tiện, hãy cẩn thận. Ngay cả sqrt của 2^60 là một số lượng lớn, mặc dù nó sẽ phù hợp với một đôi. Vấn đề là 2^60 quá lớn để vừa với một tiêu chuẩn gấp đôi, vì nó vượt quá 2^53. Vì vậy, hãy cẩn thận các vấn đề chính xác.
+ mẹo hay, cảm ơn! –
if(n1 is a perfect square)
x=(int)sqrt(n2)-(int)sqrt(n1)+1;
else
x=(int)sqrt(n2)-(int)sqrt(n1);
Không lặp lại. Phương trình:
floor(sqrt(b)) - ceil(sqrt(a)) + 1
cho biết số hình vuông hoàn hảo trong khoảng từ a lên đến b toàn diện.
* dưới 1 giây * 1 giây trên cái gì, 486 hoặc GeForce 560? –
Tại sao, 2^30 - 1? Bạn có thể tính toán 'sqrt' của các điểm cuối và tìm số lượng số nguyên trong phạm vi đó không? –