CVBB ACM Team 2020-2021:teams:wangzai_milk:wzx27:pe

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

Anonymous (anonymous@undisclosed.example.com) — 2020-05-25T17:05:03+0800

题目链接: 题意求$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$$…

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

Anonymous (anonymous@undisclosed.example.com) — 2020-05-26T13:51:11+0800

题目链接: 题意定义$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$

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

Anonymous (anonymous@undisclosed.example.com) — 2020-05-26T13:43:03+0800

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

Anonymous (anonymous@undisclosed.example.com) — 2020-05-25T10:32:58+0800

题目连接: 题意定义函数$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…