2017 ACM/ICPC Asia Regional Qingdao Online 1011 A Cubic number and A Cubic Number

阅读量：6311 次

发布时间：2019-06-22

本文共 1954 字，大约阅读时间需要 6 分钟。

A Cubic number and A Cubic Number

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)

Total Submission(s): 0 Accepted Submission(s): 0

Problem Description

A cubic number is the result of using a whole number in a multiplication three times. For example,

Input

The first of input contains an integer

Output

For each test case, output 'YES' if given

Sample Input

10 2 3 5 7 11 13 17 19 23 29

Sample Output

NO NO NO YES NO NO NO YES NO NO

Source

输入输出测试

水题呀考试的时候想那么久，其实就是一个公式，却没有看到给出的数是一个素数，否则就直接解方程达到一个公式求出来，考试的时候错了十几遍（哪来的勇气。。最好让队友暴力过了。。）

以后看题目一定要看清楚呀！！！

给出一个p,p是素数（2 <= p <=1e12），判断是否存在正整数a,b使得

a*a*a - b*b*b = p

如果存在输出YES,否则输出NO。

我们知道立方差公式：

a*a*a - b*b*b = (a-b)(a*a+a*b+b*b)

我们知道a*a*a - b*b*b = prime(素数)

所以(a-b)(a*a+a*b+b*b) = prime;

由因为prime 只能由1*prime得来。

所以prime = 1*prime

所以（a-b） = 1, (a*a+a*b+b*b) = prime , a,b必是两个相邻的整数。

设b = x,a = x+1

则（x+1）^3-x^3 = 3*x*x + 3*x + 1 = prime

3*x*x + 3*x = prime-1

x*x + x = (prime-1)/3

x(x+1) = (prime-1)/3

令：(prime-1)/3 = T；

x = int(sqrt(T)) //解出一个x

若x*(x+1) == T

则说明存在一个整数a,是的a^3 - (a-1)^3 等于当前所输入的素数。

这个a就是我们解出的x再加1.

#include 
      
         #include 
       
          #include 
        
           using namespace std;  int main()  {      int T;      scanf("%d",&T);      while(T--)      {          double n,prime;          scanf("%lf",&prime);          prime = prime - 1;          n = prime/3;          int a=(int)(sqrt(n));          int b=a+1;          if((double)a*b==n)              printf("YES\n");          else              printf("NO\n");      }      return 0;  }

转载于:https://www.cnblogs.com/l609929321/p/7537777.html

你可能感兴趣的文章