[Java] UVa 11461 Square Numbers

題目連結

題意:
每組測資給定一個區間 a, b(0 < a ≤ b ≤ 100000)
求介於 a ~ b 範圍間的 square number (平方數) 個數
也就是1, 4, 9, 16, 25,...

解法:
因為平方數是已知的
而且只需要求區間內的數量
加上測資範圍不大(最大為10萬)
可以先得到 10 萬以內的所有平方數
( 1, 4, 9 ...)

然後各自求 a, b 在陣列的對應平方數索引
( 大於 a 的最小平方數 與 小於 b 的最大平方數 )
兩者索引差就是區間內平方數個數

程式(Java):

	import java.util.*;
	public class Main {
	public static void main(String args[]) {
	Scanner input = new Scanner(System.in);
	long square[] = new long[1001];
	for (int i = 1; i <= 1000; i++)
	square[i] = i * i;
	while (input.hasNextLine()){
	int a = input.nextInt();
	int b = input.nextInt();
	int count = 0;
	int in = 1;
	int in2 = 1000;
	if (a == 0 & b == 0)
	break;
	for (; in < 1001; in++)
	if (a <= square[in]) {
	in--;
	break;
	}
	for (; in2 > 0; in2--)
	if (b >= square[in2])
	break;
	count = in2 - in;
	System.out.println(count);
	}
	}
	}

view raw UVa11461.java hosted with ❤ by GitHub