2020-2021:teams:intrepidsword:zhongzihao:project_euler
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:zhongzihao:project_euler [2021/02/10 12:50] toxel add 423 |
2020-2021:teams:intrepidsword:zhongzihao:project_euler [2021/02/20 21:05] (当前版本) toxel add 379 |
||
|---|---|---|---|
| 行 140: | 行 140: | ||
| 然后杜教筛就可以 $\mathcal{O}(n^{\frac{2}{3}})$ 解决啦。 | 然后杜教筛就可以 $\mathcal{O}(n^{\frac{2}{3}})$ 解决啦。 | ||
| + | ===== 355. Maximal coprime subset ===== | ||
| + | |||
| + | **题目大意**：求 $\{1,2,\cdots,n\}$ 的一个子集，使得其两两互质，且和最大。 | ||
| + | |||
| + | **题解**：不容易发现，不会选取某个包含超过两种小质数（$\le\sqrt{n}$）的数。大致是因为大质数非常多，因而能被小质数匹配到的相对很少，因此如果把两个小质数放一起，不如让他们给大质数作贡献（很容易凑到接近 $n$）。那么二分图最大权匹配即可。 | ||
| + | |||
| + | ===== 379. Least common multiple count ===== | ||
| + | |||
| + | **题目大意**：求满足 $x\le y,[x,y]\le n$ 的 $(x,y)$ 对数量。 | ||
| + | |||
| + | **题解**：答案为 | ||
| + | |||
| + | $$ | ||
| + | \begin{aligned} | ||
| + | &\sum_{\gcd=1}^{n}\sum_{x=1}^{n}\sum_{y=1}^{n}[(x,y)=\gcd][\frac{xy}{\gcd}\le n]\\ | ||
| + | =&\sum_{\gcd=1}^{n}\sum_{\gcd\mid d}\sum_{x=1}^{n}\sum_{y=1}^{n}\mu(\frac{d}{\gcd})[d\mid(x,y)][\frac{xy}{\gcd}\le n]\\ | ||
| + | =&\sum_{\gcd=1}^{n}\sum_{\gcd\mid d}\sum_{d\mid x}\sum_{d\mid y}\mu(\frac{d}{\gcd})[\frac{xy}{\gcd}\le n]\\ | ||
| + | =&\sum_{\gcd=1}^{n}\sum_{\gcd\mid d}\mu(\frac{d}{\gcd})S(\lfloor\frac{n}{d^2/\gcd}\rfloor)\\ | ||
| + | =&\sum_{\gcd=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{\gcd}\rfloor}\mu(i)S(\lfloor\frac{n}{i^2\gcd}\rfloor) | ||
| + | \end{aligned} | ||
| + | $$ | ||
| + | |||
| + | 其中 $S(N)$ 表示 $xy\le N$ 的 $xy$ 数量。考虑用类杜教筛求出所有 $S$（本题要带 $\log$，呃，注意到 $S=\sigma$ 的话也不用带 $\log$）。然后枚举 $i$ 根号分块即可，这部分复杂度是 $\sqrt{n}\log n$ 的。 | ||
| + | |||
| + | 这里就锻炼一下推导能力，min_25 筛应该还快一点。 | ||
| ===== 423. Consecutive die throws ===== | ===== 423. Consecutive die throws ===== | ||
| 行 179: | 行 204: | ||
| **题解**：可以猜测会有大段连续的 $1$。如果 $\gcd(n,f(n-1))=1$，那么下一个合法的位置应该和 $f(n-1)-n$ 不互质，随便算算就好。实际只需要迭代几百次（很可能中间有一个大质数）。 | **题解**：可以猜测会有大段连续的 $1$。如果 $\gcd(n,f(n-1))=1$，那么下一个合法的位置应该和 $f(n-1)-n$ 不互质，随便算算就好。实际只需要迭代几百次（很可能中间有一个大质数）。 | ||
| + | |||
| + | ===== 454. Diophantine reciprocals III ===== | ||
| + | |||
| + | **题目大意**：设有不定方程 $\frac{1}{x}+\frac{1}{y}=\frac{1}{n}$，求满足 $x<y\le N$ 的解数。 | ||
| + | |||
| + | **题解**：令 $x=x't,y=y't,(x',y')=1$，则 $\frac{1}{n}=\frac{x'+y'}{tx'y'}$。由于 $(x'+y',x')=1,(x'+y',y')=1$，因此 $(x'+y',x'y')=1$。因此 $x'+y'\mid t$。故 $t$ 的取法有 $\lfloor\frac{N}{y'(x'+y')}\rfloor$ 种。 | ||
| + | |||
| + | 答案即为 | ||
| + | |||
| + | $$ | ||
| + | \begin{aligned} | ||
| + | &\sum_{y'=1}^{+\infty}\sum_{x'=1}^{y'-1}[(x',y')=1]\lfloor\frac{N}{y'(x'+y')}\rfloor\\ | ||
| + | =&\sum_{d=1}^{+\infty}\mu(d)\sum_{y'=1}^{+\infty}\sum_{x'=1}^{y'-1}[d|(x',y')]\lfloor\frac{N}{y'(x'+y')}\rfloor\\ | ||
| + | =&\sum_{d=1}^{+\infty}\mu(d)\sum_{y'=1}^{+\infty}\sum_{x'=1}^{y'-1}\lfloor\frac{\frac{N}{d^{2}}}{y'(x'+y')}\rfloor | ||
| + | \end{aligned} | ||
| + | $$ | ||
| + | |||
| + | 枚举 $d$，枚举 $y'$，和式根号分块，即可达到较好的时间复杂度。 | ||
| ===== 479. Roots on the Rise ===== | ===== 479. Roots on the Rise ===== | ||
| 行 238: | 行 281: | ||
| 最后的答案可以通过一个简单的数位 $dp$ 得到，这里就不再赘述了。 | 最后的答案可以通过一个简单的数位 $dp$ 得到，这里就不再赘述了。 | ||
| + | |||
| + | ===== 495. Writing n as the product of k distinct positive integers ===== | ||
| + | |||
| + | **题目大意**：设 $S(n,m)$ 为将 $n$ 表示成 $m$ 个互不相同的整数乘积的方案数，求 $S(n,m)$。 | ||
| + | |||
| + | **题解**：考虑容斥。枚举 $m$ 的所有划分，表示每个子集中的所有整数相等，子集间是否相等没关系。注意到各个不同的位置本质相同，因此不需要真的枚举划分，而只需要枚举划分数即可。复杂度为 $P(m)$。注意最后答案要除以一个阶乘。若划分为整个集合，其容斥系数为 | ||
| + | |||
| + | $$ | ||
| + | C(m)=\begin{cases} | ||
| + | &1&(m=1)\\ | ||
| + | &-\sum_{P\text{ is a partition of M},P\neq\{M\}}\text{coe}(P)&(m>1) | ||
| + | \end{cases} | ||
| + | $$ | ||
| + | |||
| + | 其中，$\text{coe}(P)$ 表示划分 $P$ 的容斥系数。若划分并非是整个集合，那么 $\text{coe}(P)=\prod_{Q\in P}C(|Q|)$。可以证明，这样的容斥系数恰使得所有数互不相同的方案贡献为 $1$，其它方案贡献为 $0$。 | ||
| + | |||
| + | 计算某个方案时，可以注意到是一个无限背包 dp。 | ||
| + | |||
| + | **update**：事实上，可以证明 $C(m)=(-1)^{m-1}(m-1)!$。考虑数学归纳法，枚举 $1$ 所在的子集。注意到 $m\ge2$ 时， | ||
| + | |||
| + | $$ | ||
| + | \begin{aligned} | ||
| + | &\sum_{P\text{ is a partition of M}}\text{coe}(P)\\ | ||
| + | =&\sum_{P\text{ is a partition of M},P\neq\{M\}}\text{coe}(P)\\ | ||
| + | &-\sum_{P\text{ is a partition of M},P\neq\{M\}}\text{coe}(P)\\ | ||
| + | =&0 | ||
| + | \end{aligned} | ||
| + | $$ | ||
| + | |||
| + | 因此 $C(m)=-C(m-1)\cdot{m-1\choose m-2}\cdot1=(-1)^{m-1}(m-1)!$。 | ||
| ===== 515. Dissonant Numbers ===== | ===== 515. Dissonant Numbers ===== | ||
2020-2021/teams/intrepidsword/zhongzihao/project_euler.1612932605.txt.gz · 最后更改: 2021/02/10 12:50 由 toxel
