立方数差
?题面
?
题目描述
给出一个质数 \(p\)，要求你判断这个质数是否是两个立方数的差，即判断是否存在正整数 \(a, b\) 满足 \(a^3-b^3=p\)。
输入格式
从文件 cubicp.in 中读入数据。
多组数据。
第一行给出一个 \(T\)，表示有 \(T\) 组数据。
接下来 \(T\) 行，每行一个质数 \(p\)。
输出格式
输出到文件 cubicp.out 中。
输出 \(T\) 行，对于每个数如果是立方差数，输出 YES，否则输出 NO。
样例
样例输入
5
2
3
5
7
11
样例输出
NO
NO
NO
YES
NO
数据范围与提示
对于 \(30\%\) 的数据， \(2\leq p\leq 100\)；
对于 \(60\%\) 的数据， \(2\leq p\leq 10^6\)；
对于 \(100\%\) 的数据， \(2\leq p\leq 10^{12}\) ， \(1\leq T\leq 100\) ，并且保证每个 \(p\) 均为质数。
分析
?立方差公式：\(a^3-b^3=(a-b)\times(a^2+ab+b^2)\)
根据题意（doge），我们可以知道 \(p\) 是一个质数，且\(p=a^3-b^3\)。
那么，
\[p = (a-b)\times (a^2+ab+b^2)
\]
所以根据因式分解的性质(?)可以知道
\[a-b=1
\]
（PS：因为一个质数的因式只有它本身和1，并且如果 \(a-b=p\) 的话，会有 \(a^3-b^3=a-b\) 的离谱情况，所以 \(a-b=1\)）
那么我们只需要枚举 \(a\)，通过 \(a-b=1\) 推出 \(b\), 再以 \(a^3-b^3=p\) 来判断是否成立即可。
（PS： \(a\) 大概从 \(1\) 枚举到 \(\frac{p}{2}\)，就可以了（吧？））
但是，因为 \(a-b=1\) ，我们可以得到
\[\begin{array}{} p&=&(a-b)\times (a^2+ab+b^2)\\&=&a^2+ab+b^2\\&=&a^2-2ab+b^2+3ab\\&=&(a-b)^2+3ab\\&=&1+3a(a-1) \end{array}
\]
再结合 \(p\) 是质数，可以得到 \(p-1\) 是 3 的倍数。
进一步地，有
\[\frac{p-1}{3} = a(a-1)
\]
那么
\[a-1\leq \sqrt \frac{p-1}{3}\leq a
\]
所以，有
\[\lfloor\sqrt \frac{p-1}{3}\rfloor\times\lfloor\sqrt\frac{p-1}{3}+1\rfloor=a(a-1)=p
\]
至此，推理完毕。
Code
?#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T, p;
int main(void) {
freopen("cubicp.in", "r", stdin);
freopen("cubicp.out", "w", stdout);
cin >> T;
while (T--) {
cin >> p;
p -= 1;
if (p % 3 != 0)
cout << "NO" << endl;
else {
p /= 3;
ll t = sqrt(p);
if (t * (t + 1) == p)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
return 0;
}