2018-07-14 11:48:39

$$[gcd(i,j)=1]=\sum_{d|gcd(i,j)}\mu(d)$$

$\mu$函数有个性质

$$\sum_{d|n}\mu(d)=[n=1]$$

# 例1

$$=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\mu(d)$$

$$=\sum_{d=1}^{n}\mu(d)*\lfloor\frac{n}{d}\rfloor*\lfloor\frac{m}{d}\rfloor$$

# 例2

$$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k]\ \ \ \ (n<m)$$

$$=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]$$

# 例3

$$\sum_{i=1}^{n}\sum_{j=1}^{m}ij[gcd(i,j)=k]\ \ \ \ (n<m)$$

$$=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}ij[gcd(i,j)=1]*k^2$$

$$=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}ij\sum_{d|gcd(i,j)}\mu(d)*k^2$$

$$=\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)*d^2\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor}ij*k^2$$

$$=k^2*\sum_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)*d^2\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}i\sum_{j=1}^{\lfloor\frac{m}{kd}\rfloor}j$$

# 例4

$$lcm(i,j)=\frac{i*j}{gcd(i,j)}$$

$$=\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i*j}{d}*[gcd(i,j)=d]$$

$$=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i*j*d*[gcd(i,j)=1]$$

$$=\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i*j*d\sum_{k|gcd(i,j)}\mu(k)$$

$$=\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)*k^2\sum_{i=1}^{\lfloor\frac{n}{dk}\rfloor}i\sum_{j=1}^{\lfloor\frac{m}{dk}\rfloor}j$$

$$=\sum_{d=1}^{n}d\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)*k^2*f(\lfloor\frac{n}{T}\rfloor)*f(\lfloor\frac{m}{T}\rfloor)$$

$$=\sum_{T=1}^{n}f(\lfloor\frac{n}{T}\rfloor)*f(\lfloor\frac{m}{T}\rfloor)\sum_{d|T}d*\mu(\frac{T}{d})*(\frac{T}{d})^2$$

$$=\sum_{T=1}^{n}f(\lfloor\frac{n}{T}\rfloor)*f(\lfloor\frac{m}{T}\rfloor)\sum_{d|T}d*\mu(d)*T$$

em$\dots$貌似没法用狄利克雷卷积

$$\sum_{d|T}d*\mu(d)*T$$

$$\sum_{d|T}d*\mu(d)$$

$$F(a)=\sum_{d|a}d*\mu(d)$$

$$F(b)=\sum_{d|b}d*\mu(d)$$

$\mu(a$的某个因子$k)*\mu(b$的某个因子$j)=\mu(k*j)$

$$F(1)=1$$

$$F(a)=1-a$$ 如果$a\perp b$，则

$$F(a*b)=F(a)*F(b)$$

$$F(a*b)=F(a)$$

void sieve() {
F[1]=sum[1]=1;
for (int i=2;i<=10000000;i++) {
if (!flag[i]) prime[++cnt]=i,F[i]=1-i;
for (int j=1;j<=cnt&&i*prime[j]<=10000000;j++) {
flag[i*prime[j]]=1;
if (i%prime[j]==0) {//不互质
F[i*prime[j]]=F[i];
break;
}
F[i*prime[j]]=F[i]*F[prime[j]];//互质
}
sum[i]=sum[i-1]+F[i]*i;
}
}

$$=\sum_{T=1}^{n}f(\lfloor\frac{n}{T}\rfloor)*f(\lfloor\frac{m}{T}\rfloor)\sum_{d|T}d*\mu(d)*T$$

# 例5

$$\sum_{i=1}^{n}\sum_{j=1}^{m}d(i*j)$$

$$d(i*j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$$

# 练习

## 练习2

$$\prod_{i=1}^{n}\prod_{j=1}^{m}f[gcd(i,j)]\ \ \ (n,m\leq 10^6,T\leq 1000)$$

$f$是斐波那契数列

## 练习3

$$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)^k\ \ \ (n,m\leq 5*10^6,T\leq 2000)$$

• star
首页