AtCoder题解

jcs_pp · 2025-03-21 19:14:52 · 个人记录

ABC397

D-Cubes

思路： 我们要找到 x^3-y^3=n ，我们发现 (x-y)(3(x+y)^2+(x-y)^2))=4(x^3-y^3)=4n ，所以我们令 x+y=a,x-y=b 则 b^3(3a^2+b^2)

我们遍历 b ， b<=10^6 ，因为 b^3<=10^{18} ,求出 a ，再求 x=(a+b)/2,y=(a-b)/2 ，如果没问题就可以输出了

代码：

#include <bits/stdc++.h>
using namespace std;
long long n,a,b;
long long P_cube(long long x)
{
    long long p_cube=sqrt(x);
    if(p_cube*p_cube!=x) return -1;
    return p_cube;
}
int main()
{
    cin>>n;
    n=4*n;
    for(b=1;b*b*b<=n;b++)
    {
        if(n%b>0) continue;
        a=n/b-b*b;
        if(a%3!=0) continue;
        a/=3;
        a=P_cube(a);
        if(a==-1) continue;
        if(a%2!=b%2) continue;
        long long x=(a+b)/2,y=(a-b)/2;
        if(x<1||y<1) continue;
        cout<<x<<' '<<y<<'\n';
        return 0;
    }
    cout<<-1;
    return 0;
}