โจทย์: นับจำนวนใน [L, R] ที่มีตัวหารเป็นจำนวนคี่
จากบทความก่อน: จำนวนตัวหารคี่ ⟺ เป็น Perfect Square
→ นับ Perfect Squares ในช่วง [L, R]
สูตร
Count = ⌊√R⌋ - ⌊√(L-1)⌋
ตัวอย่างโค้ด
public class Demo {
public static int countPerfectSquaresInRange(int L, int R) {
if (L > R) return 0;
// floor(sqrt(R)) - floor(sqrt(L-1))
int sqrtR = (int) Math.sqrt(R);
int sqrtL = (int) Math.sqrt(L - 1);
return sqrtR - sqrtL;
}
public static void main(String[] args) {
int L = 55, R = 1000;
System.out.println("Range: [" + L + ", " + R + "]");
System.out.println("Count: " + countPerfectSquaresInRange(L, R));
// Verify by listing
System.out.print("Squares: ");
for (int i = (int)Math.ceil(Math.sqrt(L)); i*i <= R; i++) {
System.out.print(i*i + " ");
}
System.out.println();
}
}
ผลลัพธ์
Range: [55, 1000] Count: 24 Squares: 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625 676 729 784 841 900 961
คำอธิบาย
- Perfect squares ใน [55, 1000]: 8²=64 ถึง 31²=961
- Count = 31 - 7 = 24 (√1000≈31.6→31, √54≈7.3→7)
- Time: O(1), Space: O(1)
ขยาย: Long Range
public static long countPerfectSquaresInRangeLong(long L, long R) {
long sqrtR = (long) Math.sqrt(R);
while ((sqrtR + 1) * (sqrtR + 1) <= R) sqrtR++; // adjust up
while (sqrtR * sqrtR > R) sqrtR--; // adjust down
long sqrtL = (long) Math.sqrt(L - 1);
while ((sqrtL + 1) * (sqrtL + 1) <= L - 1) sqrtL++;
while (sqrtL * sqrtL > L - 1) sqrtL--;
return sqrtR - sqrtL;
}
ใช้ loop ปรับค่า sqrt ให้แม่นยำ (Math.sqrt อาจมี floating point error สำหรับ long ใหญ่)
