降维打击(?)
2024-02-24 16:15:05
发布于:广东
15阅读
0回复
0点赞
版本更新了!!!!!
时间复杂度:(未知,不超过O(n3logn))
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node{
int cube, i, j, k;
}ans[100005];
int ct, n;
bool cmp(node a, node b){//cmp
if(a.cube == b.cube){
if(a.k == b.k){
if(a.j == b.j) return a.i < b.i;
return a.j < b.j;
}return a.k < b.k;
}
return a.cube < b.cube;
}int pow3(int x){//立方
return x * x * x;
}
int get_(int x){//二分
int left = 1, right = n;
while(left < right){
int mid = (left + right) / 2;
if(pow3(mid) < x) left = mid + 1;
else right = mid;
}return left;
}
int main(){
cin >> n;
for(int i = 2; i <= n; i++){
for(int j = 2; j <= i; j++){
int l = get_(pow3(i) + pow3(j)), r = get_(pow3(i) + pow3(j) * 2);//得出确定两个数时的答案范围
for(int _ = l; _ <= r; _++){//遍历
int k = pow3(_) - pow3(i) - pow3(j);
int left = 1, right = n;
while(left <= right){
int mid = (left + right) / 2;
if(pow3(mid) == k){
if(mid <= j && _ <= n && mid >= 2) ans[++ct] = {_, i, j, mid};//如果k是一个整数的立方且符合条件,就存储
break;
}
if(pow3(mid) > k) right = mid - 1;
else left = mid + 1;
}
}
}
}sort(ans + 1, ans + ct + 1, cmp);//排序
for(int i = 1; i <= ct; i++) printf("Cube = %d, Triple = (%d,%d,%d)\n", ans[i].cube, ans[i].k , ans[i].j, ans[i].i);//输出
return 0;
}
这下真的达成当n=1000时也能轻松输出了
拉满了 真的拉满了
与之前的区别:在确定两个数后,k的范围是2~j,
结果的范围是sqrt3(i3+j3)~sqrt3(i3+2j3),明显比k小,所以我们遍历结果更好
全部评论 1
6
2024-02-23 来自 广东
0
有帮助,赞一个