【HDU6216】 A Cubic number and A Cubic Number 和广工的加强版

题目传送门_杭电版

题目传送门_广工版

广工版的是杭电版的加强版。

题意：判断一个质数是否是两个整数的立方差 ---- 数学题

题解：

根据立方差公式：$a^3 - b^3 = (a - b)(a^2 + ab + b^2)$

且 p 为质数

所以 $(a - b)(a^2 + ab + b^2)$ 其中任意一括号为 1，另一括号则为 p。

经计算检验（这里就不写啦），得 $(a - b) = 1$，$(a^2 + ab + b^2) = p$ 。

因为$(a - b) = 1$，所以两个整数a，b必然是相邻的，且通过计算，1e6的立方减去 999,999的立方已经大于1e12。

因此可以开个保存两个相邻整数的立方差，大小为1e6的数组保存立方差的值，然后用二分搜索该数组就可以。

但是！

广工版的题目 p 的范围是1e15，要使得立方差为1e15得要开到1e7的立方，这样就会爆long long。所以上述方法已经不够用了。

让我们回到 $(a - b) = 1$，$(a^2 + ab + b^2) = p$ 这条式子。

根据前一条式子可以把后面一条式子化成： $3b^2 + 3b + 1 = p$

把 b 当作未知量，把 p 当作常数，可把式子堪称一元二次方程了，可以弄出

$\Delta = 12p - 3$

然后根据求根公式可以写成：$ b = \frac{-3 \pm \sqrt{12p - 3}}{6}$

所以只需要验证两个条件：

1.$12p - 3$ 开方后是一个整数

2.$12p - 3$ 开方后 - 3 能否被 6 整除就可以了（因为b是正整数）

// 杭电原题：http://acm.hdu.edu.cn/showproblem.php?pid=6216

// 广工加强题：https://ac.nowcoder.com/acm/contest/3036/K

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

typedef long long LL;

int T;

LL p, ans[9000006];

void init(){

    for(LL i = 2; i <= 9000000; i++){

        ans[i - 1] = i * i * i - (i - 1) * (i - 1) * (i - 1);

    }

}

bool check(LL p){

    double a = sqrt(12 * p - 3);

    long long b = sqrt(12 * p - 3);

//    printf("a - b:%.16f, b:%lld\n", a - b, b);

    if(a - b < 0.000001 &&((b - 3) % 6 == 0) return true;

    else return false;

}

int main()

{

    // 搜索做法

    init();

    scanf("%d", &T);

    while(T--){

        scanf("%lld", &p);

        bool ok = false;

        int left = 1, right = 1000000;

        while(left <= right){

            int mid = (left + right) / 2;

            if(ans[mid] == p) { ok = true; break; }

            else if(p < ans[mid]) right = mid - 1;

            else left = mid + 1;

        }

        if(ok) printf("YES\n");

        else printf("NO\n");

    }

    // 数学解法

    scanf("%d", &T);

    while(T--){

        scanf("%lld", &p);

        if(check(p)) printf("YES\n");

        else printf("NO\n");

    }

    printf("i:%d num:%lld\n", 9000000, ans[8999999]);

    return 0;

}

巴特西

【HDU6216】 A Cubic number and A Cubic Number 和广工的加强版

最新文章

热门文章

巴特西

【HDU6216】 A Cubic number and A Cubic Number 和 广工的加强版

最新文章

热门文章

【HDU6216】 A Cubic number and A Cubic Number 和广工的加强版