题解：AT_abc397_d [ABC397D] Cubes

· · 题解

1.前言

这一道题，乍一眼看，题面十分清晰：

给你一个 N， 找出两个数 (x,y) ，使得 x^3-y^3=N 。

你可能会想到直接枚举 x ，通过公式 y=\sqrt[3]{n-x^3} 直接求出 (x,y) ，但是你很快明白，这是不可能滴，因为数据范围 1 \le N \le 10^{18} ！

这样， x 的范围是多少呢？

想象一个棱长为 x 的立方体，它的右前上方缺了一个立方体角，棱长为 y ——它就是 N ，此时，无论 y 有多大 (y<x) ，这个 N 的左面有一个完整的长方体： a=x,b=x-y,c=x ，则 N > V_{Rec.} \ge x^2 ，由此可知， x < \sqrt{N} \le 10^9 ，会TLE爆掉。

2.优化

要想解决这个问题，一定要老老实实遍历一个元素，既然 x 不行，那 y 也不抱希望了。怎么办呢？

联想之前的长方体，宽度 b 可以遍历，为了方便，令其为 a ，可知 a=x-y ，现在我们需要推导 a 的范围。

我们在之前构造的 N 中，它的左后下方有一个 V=a^3 的立方体，说明 a<\sqrt[3]{N} \le 10^6 。

时间复杂度超过 O(10^8) 就会爆，现在循环遍历 a ，循环内部留给我们的时间只有 O(100) ，所以，我们只能用二分算法枚举 a ，时间复杂度 O(\log_{2}10^9) \approx O(30) 。

3.long long问题

利用 N 图推导出公式 a^3+3(x\times(x-1)\times a) 为 N ，这个公式的最大值约为 10^{24} ，直接超longlong。

所以，我们定义 m=\frac{n-a^3}{3} ，让二分够 m ，则 r 初值可从 10^9 降为 \sqrt{m \div i}+i 。

4.AC code

#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