CVBB ACM Team

求#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|t(n)$，则$p|t(n+kp)且p|t(-n+kp)$

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

$p|t(-n+kp)$同理

2、