Difference between revisions of "Training 4: Number Theory"

From EOJ Wiki
Jump to navigation Jump to search
(Undo revision 3643 by Xiejiadong (talk))
 
(One intermediate revision by the same user not shown)
(No difference)

Latest revision as of 15:42, 12 May 2019

Problem A

题意: $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}lcm(i,j)$

题解: 原式=$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{i \times j}{gcd(i,j)} = \sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{\frac{n}{k}}\sum\limits_{j=1}^{\frac{m}{k}}i \times j[gcd(i,j)=k]$ 然后莫比乌斯反演得$\sum\limits_{k=1}^{n}mu[i] \times (1+...+\frac{n}{k}) \times (1+...+\frac{m}{k})$ 然后数论分块求和

Problem B

题意: 求第$n$个不是完全平方数的正整数倍的数

题解: 考虑容斥求出$n$以内有多少是完全平方倍数,枚举平方因子$i$贡献为$mu[i] \times n/(i*i)$因此二分每趟是$O(sqrt(n))$的,复杂度绰绰有余。

Problem C

题意: $\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}\sum\limits_{k=1}^{min(i,j)}k[k | i, k | j且\sum k \le a]$

题解:这道题想爆。$=\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}\sum\limits_{k=1}^{min(i,j)}k[k | gcd(i,j)且\sum k \le a]$先考虑没有$\le a$的情况。$f(i)$表示$i$的因数和。$g(n)=\sum\limits_{n|d}mu[d/n] \cdot \frac{n}{d} \cdot \frac{m}{d}$表示$gcd(i,j)=n$的个数。原式=$\sum\limits_{i=1}^{n}f(i)g(i)=\sum\limits_{i=1}^{n}f(i)\sum\limits_{i|d}mu[d/i] \cdot \frac{n}{d} \frac{m}{d}=\sum\limits_{d=1}^{n}\frac{n}{d}\frac{m}{d}\sum\limits_{i|d}f(i)mu[d/i]$。为了数论分块搞这个式子我们需要$F(i)$的前缀和。记$F(i)=f*mu$。只有当$f(i) \le a$时对答案做出贡献。然后就是离线操作,每次把新符合条件的$f(i)$枚举倍数新加到维护$F(i)$前缀和的树状数组中,然后再数论分块求和。复杂度$O(sqrt{(n)}logn+nsqrt{(n)})$


Problem D

题意: 给出$a_i$求有多少$b_i \le a_i$使得任意区间$gcd \ge 2$

题解:这道题当时多校补题的时候想爆。考虑容斥求出整个$gcd=k$的情况数$F(k)$,然后答案为$\sum\limits_{i=2}^{k}F(i)$。发现$G(k)=\prod\limits_{i=1}^{n}{a_i/k}$是容斥中对应$gcd>=k$的式子,且$k$包含奇数素因子为正,偶数为负,发现其和莫比乌斯函数刚好是相反关系。(个人理解莫比乌斯函数就是整除偏序上的容斥)。每一次计算都一个一个值算$G(k)$太蠢了。应该将$a_i$转换成$cnt[a_i]++$再使用前缀和,然后一段一段加,每段长度为$i$,这样相同段的$n/i$都是一样的。复杂度就是那个著名的级数$O(nlogn)$了。


Problem E

题意: $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}(n \mod i)(m \mod j)[i \not =j]$

题解:$F(i)\sum\limits_{i=1}^{n}n \mod i = \sum\limits_{i=1}^{n}n-i\frac{n}{i}, G(i)=\sum\limits_{i=1}^{n}(n \mod i)^2=完全平方展开得到类似可以分块求和的式子$,答案$F(n)F(m)-G(n)$。