CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

题目链接:[[https://projecteuler.net/problem=216]]

=== 题意 ===
求$2\le n \le 5e7$，有多少个$n$满足$t(n)=2n^2-1$是个质数

=== 题解 ===
先令$t[i]=2i^2-1$

从$2$开始枚举，用类似埃式筛的思想，如果$t[i]\gt 1$，则令$t[i+k\times t[i]] /= t[i],t[-i+k\times t[i]] /= t[i]$，如果$t[i]=2i^2-1$，则答案个数加一

上述算法的正确性需要证明几个关于$t(n)=2n^2-1$的性质:

1、若$p\mid t(n)$，则$p|mid t(n+kp)且p\mid t(-n+kp)$

证明:
$$
\begin{aligned}
t(n+p)-t(n)
& =2(n+p)^2-2n^2 \\
& =2p(2n+p) \\
\end{aligned}
$$
若$p\mid t(n)$，又因为$p\mid (t(n+p)-t(n))$，所以有$p\mid t(n+p)$，从而有$p\mid t(n+kp)$

$p\mid t(-n+kp)$同理

2、在上述算法过程中，枚举到i时，$t[i]$要么等于$1$要么是一个质数

证明：

假设$2,3,..,i-1$都满足该性质

对于$i$，反设$t[i]$可以分解为多个质数相乘，$t[i]=p_1,..,p_k\; (k>1)$，记最小的质数为$p$

若$p\lt i$，则一定被$t[i-p]$筛过，矛盾

若$p==i$，显然$i\nmid 2i^2-1$，矛盾

若$i\lt p \lt 2i$，若$p=i+1$，显然$p\nmid 2i^2-1$，否则$i+1\lt p \lt 2i$则一定被$t[-i+p]$筛过，矛盾

若$p\ge 2i$，则存在$q\ge p$，使得$pq \mid 2i^2-1$，但$pq\ge 4i^2$，矛盾

证毕

=== 代码 ===
<code cpp>
    rep(i,2,n) a[i] = 2LL*i*i-1;
    rep(i,2,n){
        if(a[i]==2LL*i*i-1) ans++;
        if(a[i]>1){
            ll p = a[i];
            for(ll j=i+p;j<=n;j+=p){
                if(a[j]%p==0) a[j]/=p;
            }
            for(ll j=-i;j<=n;j+=p){
                if(j>0 && a[j]%p==0) a[j]/=p;
            }
        }
    }
</code>

CVBB ACM Team

用户工具

站点工具

页面工具