立方数差

立方数差 ?
题面

?

题目描述

给出一个质数 \(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;
}

立方数差

上一篇:秦殇的res00.lib 相关信息


下一篇:vue-router 路由