https://wiki.cvbbacm.com/ 2026-04-30T03:42:05+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-05-25T17:05:03+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:wangzai_milk:wzx27:pe:201&rev=1590397503&do=diff 题目链接:<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)$$t[i]$$1$$2,3,..,i-1$$i$$… text/html 2020-05-26T13:51:11+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:wangzai_milk:wzx27:pe:207&rev=1590472271&do=diff 题目链接:<https://projecteuler.net/problem=207> 题意 定义$4^t=2^t+k$是$k$的一个拆分，当且仅当$4^t,2^t,k$都是正整数，且$t$是实数。特别的当，$t$也是正整数时，称为完美拆分。定义函数$P(m)$为$1\lt k \le m$中完美拆分占所有拆分的比例 题解 拆分的式子可以化简为$2^t(2^t-1)=k$，不妨设$u=2^t$$u$$u$$2$$2^t$$t$ text/html 2020-05-26T13:43:03+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:wangzai_milk:wzx27:pe:216&rev=1590471783&do=diff 题目链接:<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)$$t[i]$$1$$2,3,..,i-1$$i$$… text/html 2020-05-25T10:32:58+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:wangzai_milk:wzx27:pe:401&rev=1590373978&do=diff 题目连接:<https://projecteuler.net/problem=401> 题意 定义函数$sigma2:x \mapsto x所有因数的平方和$，求$\sum_{i=1}^{n}sigma2(i)$对$m$取模，其中$n=10^{15},m=10^9$。 题解 考虑每个因数$k$的贡献$k^2$，那么 $$ 原式=\sum_{i=1}^{n} \left \lfloor \frac{n}{i} \right \rfloor \times i^2 = \sum_{i=1}^{\left \lfloor \frac{n}{\sqrt n+1} \right \rfloor } (\left \lfloor \frac{n}{i} \right \rfloor \times i^2) \; +\; \sum_{i=1}^{\sqrt n} (f( \left \lfloor \frac{n}{i} \right \rfloor ) - f( \left \lfloor \frac{n}{i+1} \right \rfloor )) $$ 其中$f(k)=\sum_{i…