Project Euler 291

题目

Panaitopol Primes

A prime number $p$ is called a Panaitopol prime if $p = \dfrac{x^4 - y^4}{x^3 + y^3}$ for some positive integers $x$ and $y$.

Find how many Panaitopol primes are less than $5\times10^{15}$.

解决方案

令$g=\gcd(x,y)$，那么有$x=ga,y=gb$，其中$\gcd(a,b)=1$。

将上式写成$p(x^3+y^3)=x^4-y^4$，那么可以写成：

$$p(a^2-ab+b^2)=d(a^2+b^2)(a-b)$$

那么，$a^2-ab+b^2,(a^2+b^2)(a-b)$这两个数是互质的。

因此，$p=(a^2+b^2)(a-b),d=a^2-ab+b^2$。

但是，$p$是一个质数，但是有$a^2+b^2$和$a-b$两个质因式。因此$a-b=1$。

得到$p$是形如$p=a^2+(a+1)^2$的质数。

令$f(n)=2n^2+2n+1$

那么接下来使用和216题相似的筛法：如果$p\mid f(n)$，那么$p\mid f(kp+n),p\mid f(kp-n-1)$，其中$k>0$。

原因：$f(kp+n)=2(kp+n)^2+2(kp+n)+1 = 2k^2p^2+4knp+2kp+2n^2+2n+1$。我们已经假定了$p\mid 2n^2+2n+1$，因此$p\mid f(kp+n)$成立。$p\mid f(kp-n-1)$的情况类似。

这说明只要发现$f(n)$有一个质因子$p$，就可以将它把$f(n+p),f(n+2p),\dots,f(p-n-1),t(2p-n-1),\dots$筛掉。

如果有一个数始终无法筛掉，说明它本身就是一个质数。

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll N=5e15;
const int M= sqrt(N/2)+10;
ll f[M+4];
int main(){
    int m;
    for(int i=1;i<=M;i++){
        f[i]=2ll*i*(i+1)+1;
        if(f[i]>=N){
            m=i-1;break;
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++){
        ll p=f[i];
        if(p==2ll*i*(i+1)+1) ++ans;
        if(p==1) continue;
        for(ll j=p+i;j<=m;j+=p)
            while (f[j]%p==0) f[j]/=p;
        for(ll j=p-i-1;j<=m;j+=p)
            while (f[j]%p==0) f[j]/=p;
    }
    printf("%d\n",ans);
}