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）。

CPP

#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 的时候检查一下式子。

文章操作

题目大意

思路

代码实现

相关推荐

评论

AT_abc397_d