2020-2021:teams:intrepidsword:zhongzihao:project_euler
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:intrepidsword:zhongzihao:project_euler [2021/02/19 22:35] toxel add 454 |
2020-2021:teams:intrepidsword:zhongzihao:project_euler [2021/02/20 21:05] (当前版本) toxel add 379 |
||
|---|---|---|---|
| 行 146: | 行 146: | ||
| **题解**：不容易发现，不会选取某个包含超过两种小质数（$\le\sqrt{n}$）的数。大致是因为大质数非常多，因而能被小质数匹配到的相对很少，因此如果把两个小质数放一起，不如让他们给大质数作贡献（很容易凑到接近 $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 ===== | ||
2020-2021/teams/intrepidsword/zhongzihao/project_euler.1613745353.txt.gz · 最后更改: 2021/02/19 22:35 由 toxel
