Perfect Squares in a Range
easyMath & Number Theory+10 XPTime limit 2s
A tiling company only makes square floors whose area is a perfect square (1, 4, 9, 16, …). For each range [a, b], count how many perfect squares lie between a and b, both included.
Input:
- line 1:
q - next
qlines: two integersa b
Output: q lines — the count for each range.
Constraints: 1 ≤ q ≤ 10⁴, 1 ≤ a ≤ b ≤ 10¹⁸.
Think about it: the number of squares from 1 to x is ⌊√x⌋. So the answer is ⌊√b⌋ − ⌊√(a−1)⌋. Careful: a floating-point sqrt can be off by one for numbers near 10¹⁸ — compute it, then nudge it up or down until r·r ≤ x < (r+1)·(r+1).
Sample input 1
3 1 10 4 4 5 8
Sample output 1
3 1 0
Sample input 2
1 1 100
Sample output 2
10
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).