AtCoder AT_abc397_d [ABC397D] Cubes

发布于:2025-03-16 ⋅ 阅读:(21) ⋅ 点赞:(0)

题目大意

给定一个正整数 N N N,求两个正整数 x x x y y y 满足 x 3 − y 3 = n x^3-y^3=n x3y3=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 n10181x,y2106x3y3=n(xy)(x2+xy+y2)=N(xy)[(x+y)2xy]=N(xy)[(x+y)24(x+y)2(xy)2]=N x+y=a, xy=bb(a24a2b2)=Nb43a2+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 的时候检查一下式子。