专栏文章

题解：AT_abc397_d [ABC397D] Cubes

LLuojt95
AT_abc397_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipuijvz
此快照首次捕获于
2025/12/03 18:10
3 个月前
此快照最后确认于
2025/12/03 18:10
3 个月前
查看原文

1.前言

这一道题，乍一眼看，题面十分清晰：
给你一个 NN， 找出两个数 (x,y)(x,y) ，使得 x3−y3=Nx^3-y^3=N 。
你可能会想到直接枚举 xx ，通过公式 y=n−x33y=\sqrt[3]{n-x^3} 直接求出 (x,y)(x,y) ，但是你很快明白，这是不可能滴，因为数据范围 1≤N≤10181 \le N \le 10^{18} ！
这样， xx 的范围是多少呢？
想象一个棱长为 xx 的立方体，它的右前上方缺了一个立方体角，棱长为 yy ——它就是 NN ，此时，无论 yy 有多大 (y<x)(y<x) ，这个 NN 的左面有一个完整的长方体： a=x,b=x−y,c=xa=x,b=x-y,c=x ，则 N>VRec.≥x2N > V_{Rec.} \ge x^2 ，由此可知， x<N≤109x < \sqrt{N} \le 10^9 ，会TLE爆掉。

2.优化

要想解决这个问题，一定要老老实实遍历一个元素，既然 xx 不行，那 yy 也不抱希望了。怎么办呢？
联想之前的长方体，宽度 bb 可以遍历，为了方便，令其为 aa ，可知 a=x−ya=x-y ，现在我们需要推导 aa 的范围。
我们在之前构造的 NN 中，它的左后下方有一个 V=a3V=a^3 的立方体，说明 a<N3≤106a<\sqrt[3]{N} \le 10^6 。
时间复杂度超过 O(108)O(10^8) 就会爆，现在循环遍历 aa ，循环内部留给我们的时间只有 O(100)O(100) ，所以，我们只能用二分算法枚举 aa ，时间复杂度 O(log⁡2109)≈O(30)O(\log_{2}10^9) \approx O(30) 。

3.long long问题

利用 NN 图推导出公式 a3+3(x×(x−1)×a)a^3+3(x\times(x-1)\times a) 为 NN ，这个公式的最大值约为 102410^{24} ，直接超longlong。
所以，我们定义 m=n−a33m=\frac{n-a^3}{3} ，让二分够 mm ，则 rr 初值可从 10910^9 降为 m÷i+i\sqrt{m \div i}+i 。

4.AC code

CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
    int n;
    cin>>n;
    int num=cbrt(n);
    for(int i=1;i<=num;i++)
    {
        int m=n-i*i*i;
        if(m%3) continue;
        m/=3;
        int l=1,r=sqrt(m/i)+i;
        while(l<=r)
        {
            int mid=(l+r)/2;
            int nu=i*mid*(mid-i);
            if(nu==m)
            {
                if(mid==i) break;
                cout<<mid<<' '<<mid-i;
                return 0;
            }
            if(nu<m) l=mid+1;
            else r=mid-1;
        }
    }
    cout<<-1;
    return 0;
}
——By AtCoder AC code

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...