Skills101
← All coding problems

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 q lines: two integers a 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).

Loading editor…

Log in to run and submit your code — it's free.