[HackerRank]福爾摩斯和完全平方數(Sherlock and Squares)

題目描述

華生拿了兩個整數A和B給了夏洛克·福爾摩斯，然後問他是否能夠計算出A到B(包含A和B)中完全平方數的數量。完全平方數是一個整數，可以由另一個整數的平方所得到。舉例來說，1、4、9和16可以藉由計算1、2、3和4的平方來得到。

原題網址

輸入格式

第一行輸入測試資料的數量T，範圍在1到100之間(包含1和100)。
接下來的T行，每行代表一組測試資料，包含整數A和整數B。A、B的範圍在1到10⁹之間。

輸出格式

每個測試資料輸入後，要在新的一行輸出結果。

範例輸入

範例輸出

額外解釋

第一組測試資料的範圍在3~9，其中4和9是完全平方數。
第二組測試資料的範圍在17~24，其中沒有完全平方數。

解題概念

想要計算一個數是不是完全平方數，最簡單的方法就是計算其開根號的值是否為整數。但如果是要計算一個範圍內的完全平方數，每個數字都拿來開根號一次的話實在是太浪費時間了，因此在這個地方用了一個特別快速的作法來計算一個範圍內完全平方數的數量。

整數A是範圍的下限值，整數B是範圍的上限值，我們知道這範圍內的整數(包含完全平方數)，其開根號的值必定不會小於整數A開根號或是大於整數B開根號的值。因此，只要計算整數A開根號和整數B開根號的值所形成的範圍內有多少個整數，就是完全平方數的數量了。

舉例來說，若A為3、B為9，那麼只要找√3到√9之間的整數數量即可，也就是1.732~3之間的整數。1.732~3可以找到2和3這兩個整數，所以2 * 2 = 4和3 * 3 = 9是3~9內的完全平方數。

參考答案

import java.util.Scanner;

public class Solution {

    public static void main(final String[] args) throws Exception {
        final Scanner sc = new Scanner(System.in);
        int testCase = sc.nextInt();
        while (testCase-- > 0) {
            final int a = sc.nextInt();
            final int b = sc.nextInt();

            final int sqrtACeil = (int) Math.ceil(Math.sqrt(a));
            final int sqrtBFloor = (int) Math.floor(Math.sqrt(b));
            if (sqrtBFloor >= sqrtACeil) {
                System.out.println(sqrtBFloor - sqrtACeil + 1);
            } else {
                System.out.println(0);
            }
        }
    }
}