【LSOIT2】言叶之庭 ---题解
题目传送门
【你肯定怀疑我有问题吧。】
【没有。】
【我不介意呀，反正人类，多多少少有点不正常的。】
【我知道这不正常，但真的很喜欢设计鞋子，当然，水平还不够。】
【不知不觉，我都在期待雨天。晴天里，总觉得被困在孩子气里的世界，焦虑无比。】
【在我看来，她仿佛代言了这整个世界的秘密。】
【但我，只是个孩子。】
【我还能坚持下去吗？】
【可在那段连呼吸都会痛的日子里，你却只肯埋头收集周围的声音。丝毫不肯相信我的只言片语。】
这个题放在这里，感觉有点困难了。因为这虽然是一个基础题，但是是莫比乌斯反演的基础题。
首先，莫比乌斯反演是个啥？？？
定义(1)
\[\mu(x)= \begin{cases} 1 & x=1 \\ 0 & 存在p^2|x,p\in prime\\ (-1)^k & k为只因数个数 \end{cases}\]反正就是个定义，记住就行了，虽然不知道为什么要这样定义，非常神奇。
定义(2)
\(f_1 * f_2(x) = \sum_{i|x}f_1(i)f_2(\frac{n}{i})\)
为数论函数(定义域为正整数的函数）\(f_1\)和\(f_2\)的迪利克雷卷积。
定义(3)
单位函数：\(ϵ(x)=[x=1]\)
引理(1)
若\(f_1\)和\(f_2\)为积性函数，那么\(f_1 * f_2\)也为积性函数。证明对这题没什么用，就不写了。
定理(1)（反演本质）
\(1*\mu=ϵ\)
即\(\sum_{i|x}\mu(i)=ϵ(x)\)
证明：
若\(x=1\)，显然成立
否则，令\(t=\prod_{i=1}p_i^{a_i}\)\
若\(a_i\)中有一个不为一，由\(\mu\)的定义可得，存在\(p^2|x\),所以\(\mu(t)=0\)
所以对\(1*\mu\)有贡献的只有\(a_i\)为\(0\)或\(1\)因数。
设从\(p_1\)到\(p_n\)，那么有且仅有\(i\)个\(a\)的值为１的因数为
\[\begin{pmatrix} n\\ i \end{pmatrix} \]!!!!!!!!!!
那么根据\(\mu\)的定义
\(1*\mu=\sum_{i=0}^{n}(-1)^iC_{i}^{n}\)
又根据二项式定理得
\((x-1)^n=\sum_{i=0}^{n}(-1)^iC_{i}^{n}x^{n-i}\)
令\(x=1\)得
\(1*\mu=\sum_{i=0}^{n}(-1)^iC_{i}^{n}=0\)
所以得证\(1*\mu=ϵ\)
那么介绍完毕了，这个题就可以做了
大意：给出 \(n\) , \(m\) ,\(d\) ,求在$1<x≤n ,1<y≤m $的条件下，求满足 \(gcd(x,y)=d，(x,y)的数量\)
先看式子：
\(\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=d]\)这里应该没问题。
然后为了方便计算，将\(d\)从中提出来。
\(\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[gcd(i,j)=1]\)
有没有想到莫比乌斯反演？？？
\(\sum_{i|x}\mu(i)=ϵ(x)=[x=1]\)
所以这里将\(gcd(i,j)=1\)替换成莫比乌斯反演的形式即可
\(\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}\sum_{d|gcd(i,l)}\mu(d)\)
此时来到我们熟悉的形式！
枚举\(gcd!!!\)
\(\sum_{d=1}^{n}\sum_{i=1}^{\frac{n}{kd}}\sum_{j=1}^{\frac{m}{kd}}\mu(d)\)
此时发现\(\mu(d)\)和前面两个sigma没关系了，直接提出来。
\(\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{\frac{n}{kd}}\sum_{j=1}^{\frac{m}{kd}}\)
这个时候又发现后面的sigma可以直接消掉了。
\(\sum_{d=1}^{n}\mu(d)[\frac{n}{kd}][\frac{m}{kd}]\)
然后就可以用前缀和将\(\mu(d)\)先求出来了，但是，有没有发现，\(\mu(d)\)怎么求？？？
其实只要线性筛就可以了，只是要改一下，这里直接给出代码，根据定义来理解。
void init()
{
ispri[1]=true;mu[1]=1;
for(int i=2;i<=N-10;i++)
{
if(!ispri[i])pri[++cnt]=i,mu[i]=-1;
for(int l=1;l<=cnt && i*pri[l]<=N-10;l++)
{
ispri[i*pri[l]]=true;
if(i%pri[l]==0)
{
mu[i*pri[l]]=0;
break;
}
mu[i*pri[l]]-=mu[i];
}
}
for(int i=1;i<=N-10;i++)sum[i]=sum[i-1]+mu[i];
}
然后最后就是数论分块了，代码不难，主要是莫比乌斯反演，然后在给一道经验题
P3455 [POI2007] ZAP-Queries
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=50010;
int T;
int n,m,k;
bool ispri[N];
int pri[N],mu[N],sum[N];
int cnt;
void init()
{
ispri[1]=true;mu[1]=1;
for(int i=2;i<=N-10;i++)
{
if(!ispri[i])pri[++cnt]=i,mu[i]=-1;
for(int l=1;l<=cnt && i*pri[l]<=N-10;l++)
{
ispri[i*pri[l]]=true;
if(i%pri[l]==0)
{
mu[i*pri[l]]=0;
break;
}
mu[i*pri[l]]-=mu[i];
}
}
for(int i=1;i<=N-10;i++)sum[i]=sum[i-1]+mu[i];
}
int read()
{
int x=0,s=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')s=-1;
for(;isdigit(ch);ch=getchar())x=x*10+ch-48;
return x*s;
}
signed main()
{
T=read();
init();
while(T--)
{
int res=0;
n=read();m=read();k=read();
int l,r,x=n/k,y=m/k;
if(x<y)swap(x,y);
for(int l=1;l<=y;l=r+1)
{
r=min(x/(x/l),y/(y/l));
res+=(sum[r]-sum[l-1])*(x/l)*(y/l);
}
printf("%lld\n",res);
}
return 0;
}