ภาพรวมปัญหา
ให้จำนวน N ต้องการนับคู่มี序ของจำนวนเต็มบวก (a, b) ที่ a³ + b³ = N
ตัวอย่าง
Input: N = 35
Output: 2
คำอธิบาย: (2,3) และ (3,2) — 2³+3³=8+27=35
Input: N = 100
Output: 0
แนวทางแก้ปัญหา
- วนลูป a จาก 1 ถึง ⌊∛N⌋ (cube root of N)
- คำนวณ b³ = N - a³
- คำนวณ b = ∛(b³) (ปัดเศษ)
- ถ้า b³ == b×b×b และ b > 0 ให้เพิ่ม count
โค้ดตัวอย่าง
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int cubeSum(int n) {
int count = 0;
for (int a = 1; a * a * a <= n; a++) {
int a3 = a * a * a;
int bCub = n - a3;
if (bCub <= 0) continue;
int b = round(cbrt(bCub)); // ใช้ cbrt สำหรับ cube root
if (1LL * b * b * b == bCub) {
count++;
}
}
return count;
}
int main() {
int N = 35;
cout << "Count of pairs (a,b) where a^3+b^3=N: " << cubeSum(N);
return 0;
}
ผลลัพธ์
Count of pairs of (a,b) where a^3+b^3=N: 2
หมายเหตุสำคัญ
- ใช้
cbrt()แทนpow(x, 1.0/3)เพื่อความแม่นยำ - ใช้
round()หรือตรวจสอบ b, b±1 เพราะ floating point อาจคลาดเคลื่อน - คำนวณ a³ ด้วย
1LL * a * a * aป้องกัน overflow - เงื่อนไขลูป:
a * a * a <= nแทนa < cbrt(n)เพื่อความแม่นยำ
ข้อมูลเพิ่มเติม: Taxicab Numbers
จำนวนที่เขียนเป็นผลรวมกำลังสาม 2 วิธีขึ้นไป เรียกว่า Taxicab numbers
- 1729 = 1³+12³ = 9³+10³ (Hardy-Ramanujan number)
- 4104 = 2³+16³ = 9³+15³
ความซับซ้อน
- เวลา: O(∛N)
- พื้นที่: O(1)
