2020-2021:teams:wangzai_milk:wzx27:pe:201
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:wzx27:pe:201 [2020/05/25 16:58] wzx27 |
2020-2021:teams:wangzai_milk:wzx27:pe:201 [2020/05/25 17:05] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| === 题意 === | === 题意 === | ||
| - | 求#2\le n \le 5e7#，有多少个$n$满足$t(n)=2n^2-1$是个质数 | + | 求$2\le n \le 5e7$，有多少个$n$满足$t(n)=2n^2-1$是个质数 |
| === 题解 === | === 题解 === | ||
| 行 37: | 行 37: | ||
| 若$p==i$，显然$i\nmid 2i^2-1$，矛盾 | 若$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]$筛过，矛盾 | + | 若$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$，矛盾 | 若$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.1590397102.txt.gz · 最后更改: 2020/05/25 16:58 由 wzx27
