Project Euler 659

题目

Largest prime

Consider the sequence $n^2+3$ with $n \ge 1$.
If we write down the first terms of this sequence we get:

$4, 7, 12, 19, 28, 39, 52, 67, 84, 103, 124, 147, 172, 199, 228, 259, 292, 327, 364,\dots.$

We see that the terms for $n=6$ and $n=7$ ($39$ and $52$) are both divisible by $13$.

In fact $13$ is the largest prime dividing any two successive terms of this sequence.

Let $P(k)$ be the largest prime that divides any two successive terms of the sequence $n^2+k^2$.

Find the last $18$ digits of $\displaystyle \sum_{k=1}^{10\,000\,000} P(k)$.

解决方案

根据题意，所求质数$p$必须保证存在$n$，使得下式成立：

$$\left \{\begin{aligned} & n^2+k^2\equiv 0 &\pmod p \qquad(1)\\ & (n+1)^2+k^2\equiv 0 &\pmod p \qquad(2) \end{aligned}\right.$$

对$(2)$减去$(1)$，得到$2n\equiv -1\pmod p$。

对式子两边进行平方，得到$4n^2\equiv 1\pmod p$。

将式子和$(1)$重新联立，消去$n$，得到$4k^2+1\equiv 0 \pmod p$。

也就是说，$P(k)$为$4k^2+1$的最大质因数。

最终采用和216题类似的筛法计算$P(k)$：如果$p\mid P(k)$，那么$p\mid P(tp\pm k)$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10000000;
ll mod=1000000000000000000;
ll f[N+4],a[N+4];
int main(){
    for(int n=1;n<=N;n++)
        f[n]=4ll*n*n+1;
    for(int n=1;n<=N;n++){
        ll p=f[n];
        if(p==1) continue;
        a[n]=max(a[n],p);
        for(ll j=p+n;j<=N;j+=p){
            a[j]=max(a[j],p);
            while(f[j]%p==0) f[j]/=p;
        }
        for(ll j=p-n;j<=N;j+=p){
            a[j]=max(a[j],p);
            while(f[j]%p==0) f[j]/=p;
        }
    }
    ll ans=0;
    for(int i=1;i<=N;i++)
        ans=(ans+a[i])%mod;
    printf("%lld\n",ans);
}