j063 - 11428 - Cubes
題目描述
題目給定一個正整數 N，要求找到兩個正整數 x 和 y，使得 x^3 - y^3 = N。如果找不到這樣的 x 和 y，則輸出 "No solution"。如果有多組解，則輸出 y 值最小的那組解。
解題思路
題目要求找到 x 和 y 滿足 x^3 - y^3 = N。可以對 y 進行枚舉，然後使用二分搜尋法尋找對應的 x。對於每個 y，我們需要找到一個 x 使得 x = (N + y^3)^(1/3)。由於 x 必須是整數，因此可以使用二分搜尋法在 0 到 100 的範圍內尋找 x。如果找到這樣的 x，則輸出 x 和 y，並結束搜尋。如果枚舉完所有可能的 y 值後仍然沒有找到解，則輸出 "No solution"。
複雜度分析
- 時間複雜度: O(100 * log(100))，其中 100 是 y 的最大值，log(100) 是二分搜尋的複雜度。
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
long long n,j;
long long bs(long long l,long long r){
if(l>r)return l;
long long m=(l+r)/2;
if(m*m*m-j*j*j<n)return bs(m+1,r);
else return bs(l,m-1);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n){
if(n==0)return 0;
bool ac=0;
for(j=1;j<=100;++j){
long long i=bs(0,100);
if(i*i*i-j*j*j==n){
cout << i << " " << j << "\n";
ac=1;
break;
}
}
if(!ac)
cout << "No solution\n";
}
}