hdu-2886 Special Prime---数论推导

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=2866

题目大意：

问你1到L中有多少个素数满足n^3 + p*n^2 = m^3（其中n,m为大于1的自然数）

解题思路：

首先简化成n^2 *( n + p ) = m^3

假设 n^2 和 n+p 之间有公共素因子 p , 那么 n+p = k*p , 即 n=p*（k-1）,

带进去得到 p^3 * (k-1)^2 *k = m^3 , (k-1)^2*k 肯定是不能表示成某一个数的三次幂的，

所以假设不成立，所以 n^2 和 n+p 之间没有公共素因子 p ，
 那么可以假设n=x^3 , n+p=y^3 , 相减得到 p = y^3 - x^3 = (y-x) *(y^2+y*x+x^2) ,  p是素数，
所以 y-x=1 （这不用过多解释了吧，素数的因子只有1和P，右括号肯定是大于1的数了）

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 ll n, m;

 const int maxn = +;

 int prime[maxn];

 bool is_prime[maxn];

 int sieve(int n)//返回n以内素数的个数

 {

     int p = ;

     for(int i = ; i <= n; i++)is_prime[i] = ;

     is_prime[] = is_prime[] = ;

     for(ll i = ; i <= n; i++)

     {

         if(is_prime[i])

         {

             prime[p++] = i;

             for(ll j = i * i; j <= n; j += i)is_prime[j] = ;//这里涉及i*i,必须使用long long

         }

     }

     return p;

 }

 int ans[maxn];

 int main()

 {

     sieve();

     for(int i = ; ; i++)

     {

         int t =  * i * i +  * i + ;

         if(t > )break;

         if(is_prime[t])ans[t] = ;

     }

     for(int i = ; i < maxn; i++)

         ans[i] += ans[i - ];

     while(cin >> n)

         if(ans[n])cout<<ans[n]<<endl;

         else cout<<"No Special Prime!"<<endl;

     return ;

 }