AT_abc397_d

· · 题解

在博客内阅读效果更佳：https://blog.csdn.net/ArmeriaLeap/article/details/146286412。

题目大意

给定一个正整数 N，求两个正整数 x 和 y 满足 x^3-y^3=n。

思路

直接枚举会超时，考虑把式子变形。下面是我的演算过程：

\because n\le10^{18}\\ \therefore 1\le x,y\le2\cdot10^6\\ x^3-y^3=n\\ (x-y)\cdot (x^2+xy+y^2)=N\\ (x-y)\cdot [(x+y)^2-xy]=N\\ (x-y)\cdot [(x+y)^2-\frac{(x+y)^2-(x-y)^2}{4}]=N\\ 令\ x+y=a,\ x-y=b\\ \therefore b\cdot (a^2-\frac{a^2-b^2}{4})=N\\ b\cdot \frac{3a^2+b^2}{4}=N\\ b\cdot(3a^2+b^2)=4N

所以我们可以直接枚举 N 的因数 b，因为上述式子也可以变形为 3a^2b+b^3=4N，所以 b^3<4N。接下来，我们考虑是否有一个正整数 a。可以根据式子算出 3a^2，然后看 \sqrt{a^2} 的值是否是一个正整数。

判断可以直接用 C++ 语言中的 sqrt 函数，注意需要 #include <cmath> 或者使用万能头文件。但是这个函数本质上是二分，带 log，虽然不影响通过本题，但是还是有些慢的。我曾经试过预处理，但是不行，因为把平方数打表打出来就已经超时了，所以还是用系统函数吧。

代码实现

已 AC，提交记录：Submission #63817473，其实跑得还是挺快的（6ms）。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <unordered_map>
using namespace std;

long long n;

long long sqr(long long a)
{
    long long ret = sqrt(a);
    if (ret * ret != a)
        return -1;
    return ret;
}

int main()
{
    cin >> n; n *= 4;
    for (long long b = 1; b * b * b <= n; b++)
    {
        if (n % b != 0) continue;
        long long a = n / b - 1LL * b * b;
        if (a % 3) continue; a /= 3;
        a = sqr(a); if (a == -1) continue;
        if (a % 2 != b % 2) continue;
        long long x = (a + b) / 2;
        long long y = (a - b) / 2;
        if (x < 1 || y < 1) continue;
        cout << x << " " << y << endl;
        return 0;
    }
    cout << "-1" << endl;
    return 0;
}

如有更好的做法欢迎提出！本次 D 题推式子千万别推错了，不过样例也应该过不了，所以在发现出 bug 的时候检查一下式子。