题解 | #完全平方数#

package main

import (
	"bufio"
	. "fmt"
	"io"
	"math"
	"os"
)

func main() {
	NC14733(os.Stdin, os.Stdout)
}

// https://ac.nowcoder.com/acm/problem/14733
func NC14733(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()

	// 构建满足 0 - 1000000000的整数平分根
	maxNum := int(math.Sqrt(float64(1000000000)))
	sqrtArr := make([]int, maxNum+1)
	for i := 1; i <= maxNum; i++ {
		sqrtArr[i] = i * i
	}
	// 参数输入
	var n int
	for Fscan(in, &n); n > 0; n-- {
		var l, r int
		Fscan(in, &l, &r)
		// 二分查找
		// >= l 的最左位置
		li, ri := 0, len(sqrtArr)-1
		for li <= ri {
			mid := (li + ri) / 2
			if sqrtArr[mid] >= l {
				ri = mid - 1
			} else {
				li = mid + 1
			}
		}
		lIndex := li

		//  <=r的最右位置
		li, ri = 0, len(sqrtArr)-1
		for li <= ri {
			mid := (li + ri) / 2
			if sqrtArr[mid] <= r {
				li = mid + 1
			} else {
				ri = mid - 1
			}
		}
		rIndex := ri
        // 输出答案个数
		Fprintln(out, rIndex-lIndex+1)
	}
}