给定一个n,问gcd为质数的对数
n,m\le10^7,1\le x,y \le n
欧拉函数解法
- 考虑枚举每个质数g
- 对于每个g,有多少对数(x,y)的gcd(x,y)=g,即为\phi[\frac{n}{g}]
- 线性递推求欧拉函数即可,注意\phi(1)设为0,x=y且 x 和 y 为素数的情况只有一对满足
- 前面的答案×2 是最后的答案?
- 漏掉了x=y且 x 和 y 为素数的情况,加上即可
莫比乌斯反演解法
若这个题x,y的数据范围不一样则必须用莫比乌斯反演了,比如BZOJ 2820(权限题)
- 设(n<m),不符合{\rm swap}(n,m)即可
- 设n以内的素数为p,一共有N个
- \sum _{isprime(p)}^{N}\sum _{i=1}^{n}\sum _{j=1}^{m}[\gcd(i,j)=p]
- \sum _{isprime(p)}^{N}\sum _{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum _{j=1}^{\left \lfloor \frac{m}{p} \right \rfloor}[\gcd(i,j)=1]
- 莫比乌斯反演可得
- \sum _{isprime(p)}^{N}\sum _{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum _{j=1}^{\left \lfloor \frac{m}{p} \right \rfloor}\sum _{ d|\gcd(i,j)}\mu(d)
- \sum _{isprime(p)}^{N}\sum _{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum _{j=1}^{\left \lfloor \frac{m}{p} \right \rfloor}\sum _{ d|i \wedge d|j }\mu(d)
- \sum _{isprime(p)}^{N}\sum _{d=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\mu(d)\left \lfloor \frac{n}{pd} \right \rfloor \left \lfloor \frac{m}{pd} \right \rfloor
- 这样直接做的复杂度是O(\frac{n}{logn}·\sqrt{n}),显然无法通过此题
- 令pd=k
- \sum _{k=1}^{n}\sum _{isprime(p)\wedge p|k}^{N}\mu(\frac{k}{p})\left \lfloor \frac{n}{k} \right \rfloor \left \lfloor \frac{m}{k} \right \rfloor
- 预处理所有k的系数即\sum _{isprime(p)\wedge p|k}^{N}\mu(\frac{k}{p}),具体方法:线性筛mobius,然后枚举质数及其倍数,求出每个系数
- 后面就是整除分块了,但对于每一块要保证n和m的值都不会变才行,即r=\min(n/(n/l),m/(m/l))
莫比乌斯反演代码
1 |
|