题目大意
给定一个正整数 N N N，求两个正整数 x x x 和 y y y 满足 x 3 − y 3 = n x^3-y^3=n x3−y3=n。
思路
直接枚举会超时，考虑把式子变形。下面是我的演算过程：
∵ n ≤ 1 0 18 ∴ 1 ≤ x , y ≤ 2 ⋅ 1 0 6 x 3 − y 3 = n ( x − y ) ⋅ ( x 2 + x y + y 2 ) = N ( x − y ) ⋅ [ ( x + y ) 2 − x y ] = N ( x − y ) ⋅ [ ( x + y ) 2 − ( x + y ) 2 − ( x − y ) 2 4 ] = N 令 x + y = a , x − y = b ∴ b ⋅ ( a 2 − a 2 − b 2 4 ) = N b ⋅ 3 a 2 + b 2 4 = N b ⋅ ( 3 a 2 + b 2 ) = 4 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≤1018∴1≤x,y≤2⋅106x3−y3=n(x−y)⋅(x2+xy+y2)=N(x−y)⋅[(x+y)2−xy]=N(x−y)⋅[(x+y)2−4(x+y)2−(x−y)2]=N令 x+y=a, x−y=b∴b⋅(a2−4a2−b2)=Nb⋅43a2+b2=Nb⋅(3a2+b2)=4N
所以我们可以直接枚举 N N N 的因数 b b b，因为上述式子也可以变形为 3 a 2 b + b 3 = 4 N 3a^2b+b^3=4N 3a2b+b3=4N，所以 b 3 < 4 N b^3<4N b3<4N。接下来，我们考虑是否有一个正整数 a a a。可以根据式子算出 3 a 2 3a^2 3a2，然后看 a 2 \sqrt{a^2} a2 的值是否是一个正整数。
判断可以直接用 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 的时候检查一下式子。