ภาพรวมปัญหา
ให้จำนวน N ต้องการนับคู่มี序ของจำนวนเต็มบวก (a, b) ที่ a² + b² = N
ตัวอย่าง
Input: N = 100
Output: 2
คำอธิบาย: (6,8) และ (8,6) — 6²+8²=36+64=100
Input: N = 11
Output: 0
แนวทางแก้ปัญหา
- วนลูป a จาก 1 ถึง ⌊√N⌋
- คำนวณ b² = N - a²
- ถ้า b² เป็นกำลังสองสมบูรณ์ (sqrt(b²) เป็นจำนวนเต็ม) ให้เพิ่ม count
- นับคู่มี序 ดังนั้น (a,b) และ (b,a) นับคนละคู่ (ถ้า a≠b)
โค้ดตัวอย่าง
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int squareSum(int n) {
int count = 0;
for (int a = 1; a * a <= n; a++) {
int bSq = n - a * a;
int b = sqrt(bSq);
if (b * b == bSq && b > 0) {
count++;
}
}
return count;
}
int main() {
int N = 5;
cout << "Count of pairs (a,b) where a^2+b^2=N: " << squareSum(N);
return 0;
}
ผลลัพธ์
Count of pairs of (a,b) where a^2+b^2=N: 122
หมายเหตุสำคัญ
- โค้ดต้นฉบับมีข้อผิดพลาด: output เขียนว่า
a^3+b^3=Nแต่คำนวณ a²+b² - ตัวแปร
bsquareควรเป็นlong longป้องกัน overflow - ใช้
a * aแทนpow(a,2)เร็วกว่าและแม่นยำกว่า
แนวทางคณิตศาสตร์ (Number Theory)
จำนวนวิธีเขียน N = a² + b² (รวมลำดับและเครื่องหมาย) เกี่ยวข้องกับการแยกตัวประกอบเฉพาะของ N:
- ถ้า N มีตัวประกอบเฉพาะ p ≡ 3 (mod 4) กับเลขชี้คี่ → 0 วิธี
- มิฉะนั้น จำนวนวิธี = 4 × (d₁(N) - d₃(N)) โดย d₁,d₃ คือจำนวนหารที่ ≡ 1,3 (mod 4)
ความซับซ้อน
- เวลา: O(√N)
- พื้นที่: O(1)
