2020-2021:teams:wangzai_milk:wzx27:pe:201

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:wangzai_milk:wzx27:pe:201 [2020/05/25 16:28]
wzx27 创建
+++ 2020-2021:teams:wangzai_milk:wzx27:pe:201 [2020/05/25 17:05] (当前版本)
wzx27
@@ 行 1: / 行 1: @@
-[https://projecteuler.net/problem=216]
+题目链接:[[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$的性质:
+、若$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)$同理
+、在上述算法过程中，枚举到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>

2020-2021/teams/wangzai_milk/wzx27/pe/201.1590395317.txt.gz · 最后更改: 2020/05/25 16:28 由 wzx27