HAOI2011 problem b
题目描述
对于给出的$n$个询问,每次求有多少个数对$(x,y)$,满足$a≤x≤b,c≤y≤d$,且$gcd(x,y) = k,gcd(x,y)$函数为x和$y$的最大公约数。
输入输出格式
输入格式:
第一行一个整数n,接下来n行每行五个整数,分别表示$a、b、c、d、k$
输出格式:
共$n$行,每行一个整数表示满足要求的数对$(x,y)$的个数
输入输出样例
输入样例#1:
2
2 5 1 5 1
1 5 1 5 2
输出样例#1:
14
3
说明
$100%$的数据满足:$1≤n≤50000,1≤a≤b≤50000,1≤c≤d≤50000,1≤k≤50000$
莫比乌斯反演
借着这道题谈一下莫比乌斯反演
莫比乌斯函数
莫比乌斯函数是一个积性函数
其定义如下
$$\mu(n)=\begin{cases}
1,n=1\\
(-1)^k=p_1p_2…p_k,p_i\in{prime}\\
0,else
\end{cases}$$
莫比乌斯函数具有以下性质
$$\sum_{d|n}\mu(d)=\begin{cases}
1,n=1\\
0,n>1
\end{cases}$$
莫比乌斯函数是积性函数
Dirichlet卷积
两个数论函数$f(x),g(x)$的卷积$(f×g(x))$定义为
$$f×g(n)=\sum_{d|n}f(d)g(\frac n d)$$
莫比乌斯反演
如果数论函数$f(x),g(x)$满足
$$f(n)=\sum_{d|n} g(d)$$
那么它们也满足
$$g(n)=\sum_{d|n}\mu(n)f(\frac n d)$$
题解
显然上面那一题就是一个比较裸的莫比乌斯反演题了
首先来看如果去掉$x,y$的下限
首先两边同时除以$k$
那么条件就变成了
$$gcd({\frac x k},{\frac y k})=1$$.
而且有
$$\sum_{d|n}\mu(d)=[n=1]$$
原来要求的是
$$\sum_{x=a}^b\sum_{y=c}^d[gcd(x,y)=k]$$
就转化为了
$$\sum_{x=1}^{b’}\sum_{y=1}^{d’}\sum_{d|(x,y)}\mu(d)$$
然后
显然就是一个除法之后向下取整求和
但是直接枚举$d$就TLE了
于是采用分块处理
但是很显然有下限,于是容斥原理
(画下图就知道了。。。)
code
|
|