HDU6216 (A Cubic number and A Cubic Number)做题笔记

发表于 | 更新于 | | 阅读次数：

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6216

这题考察的是数学思维。

一开始想用打表暴力枚举出所有（满足a^3-(a-1)^3<=2*10^12）的a^3，然后枚举b^3并判断b^3+p是否在枚举出的a^3中，但因为要开816498的long long数组内存吃不消，所以只能作罢。

其实这题是立方差公式: a^3-b^3=(a-b)*(a^2+a*b+b^2) 并且因为p为质数，所以a-b只能是1。此时带入a=b+1，可以得到p=3*b^2+3*b+1，枚举b就能得到答案了。

贴上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <cstring>
int main () {
	int T;
	bool flag=0;
	long long tmp,x;
	scanf("%d",&T);
	while (T--) {
		scanf("%lld",&x);
		flag=0;
		for (long long i=1;i<=816497;i++) {
			tmp=3*i*i+3*i+1;
			if (tmp==x) {
				flag=1;
				break;
			}
			else if (tmp>x) {
				break;
			}
		}
		if (flag) printf("YES\n");
		else printf("NO\n");
	}
}