d292 - 00386 - Perfect Cubes

🔗 前往 ZeroJudge 原題

題目描述

題目要求找出所有滿足 a^3 = b^3 + c^3 + d^3 的整數解，其中 2 <= a, b, c, d <= 200，且 b < c < d。輸出格式如題目範例所示，按照 a 的非遞減順序，以及在相同 a 的情況下，b 的非遞減順序輸出。

解題思路

此題採用暴力解法。由於 a, b, c, d 的範圍較小，可以直接使用四層迴圈枚舉所有可能的組合。外層迴圈枚舉 a，內層迴圈枚舉 b, c, d，並檢查是否滿足 a^3 = b^3 + c^3 + d^3。為了避免重複計算和提高效率，可以加入一些剪枝操作，例如在內層迴圈中，如果 b^3 + c^3 已經大於 a^3，則可以提前結束迴圈。

複雜度分析

• 時間複雜度: O(200^4) 由於使用了四層嵌套迴圈，且每層迴圈最多迭代 200 次。
• 空間複雜度: O(1) 程式只使用了常數級別的額外空間。

程式碼

#include <iostream>
using namespace std;
int main(){
	for(int a=2;a<=200;++a){
		int a3=a*a*a;
		for(int b=2;b<a;++b){
			int b3=b*b*b;
			if(b3>a3)break;
			for(int c=b+1;c<a;++c){
				int c3=c*c*c;
				if(b3+c3>a3)break;
				for(int d=c+1;d<=a;++d){
					int d3=d*d*d;
					if(b3+c3+d3==a3){
						cout << "Cube = " << a << ", Triple = (" << b << "," << c << "," << d << ")\n"; 
					}
				}
			}
		}
	}
}