题目原文：

豆豆还是觉得自己智商太低了，就又去做数学题了。一看到题，他就觉得自己可能真的一点智商都没有。便哭着跑来像 dalao 求教：如果存在正整数 A，B ，满足 A3 - B3 = x ，则称质数 x 为立方数。现在给你一个质数 x ，请判断是不是立方数，如果是请输出 “YES” ,否则输出 “NO” 。

【数据范围】

对于 40% 的数据，如果有解 A 在 10000 以内；

对于 100% 的数据，T≤1000；1≤x≤1012。

【思考】

如果是以下数据范围，怎么做？

对于 100% 的数据，T≤100000；1≤x≤1012。

题目分析：

简单的数学推导：\(P = (a - b)(a^2 + ab + b^2)\)，因为p是质数，所以一定是1*p,因为a，b都为正数，所以\(a-b=1 => a=b+1\)，带入可得\(p = 3b^2+3b+1\)。

于是可以预处理出\(b^2+b\)的值，每次去二分查找\((p - 1) / 3\)即可。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace IO{

    inline ll read(){

        ll i = 0, f = 1; char ch = getchar();

        for(; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());

        if(ch == '-') f = -1, ch = getchar();

        for(; ch >= '0' && ch <= '9'; ch = getchar()) i = (i << 3) + (i << 1) + (ch - '0');

        return i * f;

    }

    inline void wr(ll x){

        if(x < 0) putchar('-'), x = -x;

        if(x > 9) wr(x / 10);

        putchar(x % 10 + '0');

    }

}using namespace IO;

const int N = 1e6 + 5;

ll b[N], T;

inline void init(){

    for(ll i = 1; i <= 1000000; i++) b[i] = i * i + i;

}

inline bool query(ll x){

    ll l = 1, r = 1000000;

    while(l <= r){

        ll mid = l + r >> 1;

        // cout<<mid<<endl;

        if(b[mid] == x) return true;

        else if(b[mid] < x) l = mid + 1;

        else r = mid - 1;

    }

    return false;

}

int main(){

    freopen("h.in", "r", stdin);

    T = read();

    init();

    while(T--){

        ll x = read();

        if((x - 1) % 3) printf("NO\n");

        else if(query((x - 1) / 3)) printf("YES\n");

        else printf("NO\n");

    }

    return 0;

}

巴特西

NOIP模拟 cube - 数学

题目原文：

题目分析：

code

最新文章

热门文章