本文主要是介绍hdu 2866 Special Prime，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：Special Prime
题意：求范围L内满足 n^3 + p*n^2 = m^3 的素数p的个数
思路：化简一下得到 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 ， p =(x+1)^3 - x^3 = 3*x^2+3*x+1 , 暴力一下x,判断是否是素数就ok了
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
#define maxn 1000010
bool prime[maxn];
void Prime()
{memset(prime,true,sizeof(prime));prime[0]=prime[1]=0;for(int i=2;i*i<maxn;i++)if(prime[i])for(int j=2*i;j<maxn;j+=i)prime[j]=0;
}
int main()
{Prime();int n,ans,p;while(scanf("%d",&n)!=EOF){ans=0;for(int i=1;;i++){int tmp=3*i*i+3*i+1;if(tmp>n)break;if(prime[tmp])ans++;}if(ans)printf("%d\n",ans);elseprintf("No Special Prime!\n");}return 0;
}
这篇关于hdu 2866 Special Prime的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
