【project euler】思维记录

没事时做点$pe$的题,可能会发题解,可能会懒,嗯。

目前进度:

364

枚举$0x0$格式的和$0xx0$格式的数量,顺带特判一下角落剩余的格子,然后组合数求一下就可以了。

模数居然是$10^8+7$。

675

考虑狄利克雷卷积,可以得到$S(n)=\tau(n^2)$。然后考虑从$(n-1)!$推到$n!$,把$n$扔进桶里,然后每次递归利用最小质因数算答案,复杂度大概是$O(n\Omega(n))$?

601

写一下式子,就是要求$(k+1)|(n-1)$的最小$k$小于等于$31$。于是容斥一下就好了。

608

推式子出击。

$D(m,n)=\sum_{d|m}\sum_{k=1}^n \tau(kd)$

$=\sum_{d|m}\sum_{k=1}^n\sum_{x|k}\sum_{y|d}[(x,y)=1]$

$=\sum_{k=1}^n\sum_{x|k}\sum_{d|m}\sum_{y|d}[(x,y)=1]$

$=\sum_{x=1}^n\lfloor \frac{n}{k}\rfloor\sum_{d|m}\sum_{y|d}[(x,y)=1]$

$=\sum_{x=1}^n\lfloor \frac{n}{k}\rfloor\sum_{y|m}\tau(\frac{m}{y})[(x,y)=1]$

$=\sum_{x=1}^n\lfloor \frac{n}{k}\rfloor\sum_{y|m}\tau(\frac{m}{y})\sum_{i|(x,y)}\mu(i)$

$=\sum_{i|m,i\leq n}\mu(i)\sum_{d=1}^n\lfloor \frac{n}{di}\rfloor\sum_{y|\frac{m}{i}}\tau(\frac{m}{yi})$

$=\sum_{i|m,i\leq n}\mu(i)\sum_{d=1}^{\frac{n}{i}}\lfloor\frac{\lfloor \frac{n}{i}\rfloor}{d}\rfloor\sum_{y|\frac{m}{i}}\tau(\frac{m}{yi})$

$=\sum_{i|m,i\leq n}\mu(i)f(\lfloor \frac{n}{i}\rfloor)(\tau\ast I)(\frac{m}{i})$

化简到这一步就基本完成了。我们分析一下这条式子怎么求。

首先是枚举$i$,$\mu(i)$只有当$i$无平方因子时才有贡献,所以可以暴力枚举。

$\mu(i)$在暴力$dfs$质数因子时直接算出。

$f(\lfloor \frac{n}{i}\rfloor)$这个东西可以利用$h\ast id=g,g(n)=n\tau(n),h(n)=\lfloor\frac{m}{n}\rfloor$,然后杜教筛求出。

$\tau\ast I$可以用$\tau\ast I=I\ast I\ast I$,这个东西考虑组合意义就是一个数分成三个有序的数的乘积的方案数,可以写出$\tau\ast I(n)=\prod \frac{(e_i+1)(e_i+2)}{2}$,其中$n=\prod_{p_i} p_i^{e_i}$,这个也可以在$dfs$时直接求出。

于是最后就能算出$D(200!,10^{12})$了。

677

题解放博客了

657

如果不能全选的限制,答案显然就是$\sum_{i=0}^n \alpha^i=\frac{\alpha^{n+1}-1}{\alpha-1}$。有了这个限制,考虑容斥,即枚举每次至多选了几个,这样容斥一下答案就是$\sum_{i=0}^{\alpha-1} (-1)^{\alpha-i+1}\frac{i^{n+1}-1}{i-1}\binom{\alpha}{i}$,然后就做完了。

658

要求的式子是$\sum_{\alpha=1}^k \sum_{i=0}^{\alpha-1} (-1)^{\alpha-i+1}\frac{i^{n+1}-1}{i-1}\binom{\alpha}{i}$

$=\sum_{i=0}^{k-1} (-1)^{i+1}\frac{i^{n+1}-1}{i-1}\sum_{\alpha=i+1}^k (-1)^{\alpha}\binom{\alpha}{i}$。

令$F(i)=\sum_{\alpha=i+1}^k (-1)^{\alpha}\binom{\alpha}{i}$。

则$F(i)=\sum_{\alpha=i+1}^k (-1)^{\alpha}(\binom{\alpha+1}{i+1}-\binom{\alpha}{i+1})$

$=\sum_{\alpha=i+1}^k (-1)^{\alpha}\binom{\alpha+1}{i+1}-\sum_{\alpha=i+1}^k (-1)^{\alpha}\binom{\alpha}{i+1}$

$=\sum_{\alpha=i+1}^k (-1)^{\alpha}\binom{\alpha+1}{i+1}-(\sum_{\alpha=i+2}^k (-1)^{\alpha}\binom{\alpha}{i+1}+(-1)^{i+1})$

$=\sum_{\alpha=i+1}^k (-1)^{\alpha}\binom{\alpha+1}{i+1}-(F(i+1)+(-1)^{i+1})$

$=-\sum_{\alpha=i+1}^k (-1)^{\alpha+1}\binom{\alpha+1}{i+1}-(F(i+1)+(-1)^{i+1})$

$=-\sum_{\alpha=i+2}^{k+1} (-1)^{\alpha}\binom{\alpha}{i+1}-(F(i+1)+(-1)^{i+1})$

$=-(\sum_{\alpha=i+2}^k (-1)^{\alpha}\binom{\alpha}{i+1}+(-1)^{k+1}\binom{k+1}{i+1})-(F(i+1)+(-1)^{i+1})$

$=-(F(i+1)+(-1)^{k+1}\binom{k+1}{i+1})-(F(i+1)+(-1)^{i+1})$

$=(-1)^k\binom{k+1}{i+1}+(-1)^i-2F(i+1)$。

于是$F(i)$就可以$O(k)$递推了。

原式就变成$\sum_{i=0}^{k-1} (-1)^{i+1}\frac{i^{n+1}-1}{i-1}F(i)$。

所以预处理$F(i)$,原式也就可以$O(k)$递推,于是就完事了。

577

考虑到任意一个合法的正六边形都要占$3n$行,所以枚举正六边形的边长,剩下来的平移就好了。总复杂度$O(n^2)$。

696

选考复习日,有点累了,随便做道。

打了个表,发现是个多项式,$t=30$时次数是小于等于$100$的,具体懒得算了。

484

考虑 $\gcd(n,n’)$ 到底是什么。

注意到 $n’=\sum \frac{na_i}{p_i}$,其中 $n=\prod p_i^{a_i}$。于是 $\gcd(n,n’)=\prod p_i^{a_i-1}\gcd(\sum \frac{a_j\prod p_i}{p_j},\prod p_i)$。

于是 $f(n)=\gcd(n,n’)$ 是积性函数,且 $f(p^e)=p^{e-1}\gcd(p,e)$。

注意到 $f(p)=1$,令 $g(n)=1$,于是就可以使用 $\mathrm{PN}$ 筛做到 $O(\sqrt{n})$。

具体来说,就是构造 $h=\frac{f}{g}$,于是 $h$ 只在 $\mathrm{powerful\ number}$ 处有值,且 $h(p^k)=f(p^k)-\sum_{c=0}^{k-1}h(p^c)g(p^{k-c})$。

同时 $\sum_{i=1}^n f(i)=\sum_{d=1}^n [d\in \mathrm{PN}] h(d) S_g(\lfloor\frac{n}{d}\rfloor)$,于是就是 $O(\sqrt{n})$ 了。