Special Prime HDU - 2866(数论)

Give you a prime number p, if you could find some natural number (0 is not inclusive) n and m, satisfy the following expression:

We call this p a “Special Prime”.
AekdyCoin want you to tell him the number of the “Special Prime” that no larger than L.
For example:
If L =20
1^3 + 7*1^2 = 2^3
8^3 + 19*8^2 = 12^3
That is to say the prime number 7, 19 are two “Special Primes”.
Input
The input consists of several test cases.
Every case has only one integer indicating L.(1<=L<=10^6)
Output
For each case, you should output a single line indicate the number of “Special Prime” that no larger than L. If you can’t find such “Special Prime”, just output “No Special Prime!”
Sample Input
7
777
Sample Output
1
10
问有在这个L范围内有多少的素数使得这个成立，一开始看感觉很难，最后还是做出来了
来一步一步分析：

$$n^3+n^2p=m^3$$
显然 $m>n$,并且写成 $$n^2(n+p)=m^3$$
然后我观察了一下hint，发现似乎每个n都是立方数，那么， $n+p$也必须为立方数这样 $n^2(n+p)$就必然是一个立方数
设， $n=b^3$只要满足 $b^3+p=a^3$,到这里发现这个题和我之前做过的一道题类似了，则： $$p=a^3-b^3=(a-b)(a^2+ab+b^2)$$
所以 $a-b=1$,则: $$p=3b^2+3b+1$$ 只要判断 $12p-3$是一个平方数即可

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 1000005
using namespace std;
bool p[N];
int ans[N];
bool check(int x)
{int k=12*x-3;int m=(int)sqrt(k);return m*m==k;
}
void init()
{p[0]=p[1]=true;for(int i=2;i<N;i++){if(!p[i])for(int j=i+i;j<N;j+=i)p[j]=true;}for(int i=1;i<=1000000;i++){if(!p[i]&&check(i))ans[i]++;ans[i]+=ans[i-1];}
}int main()
{init();int l;while(scanf("%d",&l)==1){if(ans[l]==0)printf("No Special Prime!\n");elseprintf("%d\n",ans[l]);}return 0;
}