题解-hdu2866 Special Prime

Problem

hdu-2866

题意:求区间\([2,L]\)有多少素数\(p\)满足\(n^3+pn^2=m^3\),其中\(n,m\)属于任意整数

Solution

原式等价于\(n^2(p+n)=m^3\)


可证当\(p|\gcd(n^2,n+p)\)时,无解,因为当\(n=k\cdot p\)时

\(k^2p^3+k^3p^3=m^3\)

\(m=p\sqrt [3]{k^2+k^3}\)可证无整数解,对于这一点,证明如下

\(k^2+k^3=k^2(1+k)\)

假如\(1+k\)为立方数,则要求\(k^2\)也为立方数,即\(k\)为立方数,这样的话,\(k\)与\(k+1\)都为立方数,这是不存在的(除非\(k=0\),但这样的话不满足我们的题设了)

假如\(1+k\)不是立方数,则要求\(k^2\)里头必须有因数来填补\(1+k\)不能被开立方根的空缺,但\(\gcd(k,1+k)=1\),所以不可能有因数来填补空缺

即\(m=p\sqrt[3]{k^2+k^3}\)无整数解

即\(n\not =k\cdot p\),即\(p\)不为\(\gcd(n^2,n+p)\)的因数,即它俩互质


若\(n=x^3,n+p=y^3\),则\(m=x^2y,p=y^3-x^3\)

则\((y-x)|p\),由于\(p\)是质数,所以\(y=x+1\)

代回去发现\(p=y^3-x^3=(x+1)^3-x^3\)

所以可以枚举\(x\),并使得计算出的\(p\)为质数即可

Code

#include <bits/stdc++.h>
#define rg register const int N=1001000;
int is[N],f[N],n; void prework(){
for(rg int i=2;i<1010;++i)if(!is[i])
for(rg int j=i*i;j<N;j+=i)is[j]=1;
for(rg int i=1;;++i){
int v=1ll*(i+1)*(i+1)*(i+1)-1ll*i*i*i;
if(v<N)f[v]=(is[v]?0:1);else break;
}for(rg int i=1;i<N;++i)f[i]+=f[i-1];
} int main(){
prework();
while(~scanf("%d",&n))
if(n<7)puts("No Special Prime!");
else printf("%d\n",f[n]);
return 0;
}
上一篇:Visual Studio 如何恢复默认设置


下一篇:2013长春网赛1004 hdu 4762 Cut the Cake