Description
题目链接:BZOJ 2301
求如下式子的值:
本题 $T$ 组数据。
数据范围:$1\le T,x,y,n,m,k\le 5\times 10^4$
Solution
根据容斥原理,原式可以分成 $4$ 块来处理,每一块的式子形式都为
考虑化简该式子
因为 $\gcd(i,j)=1$ 时对答案才用贡献,于是我们可以将其替换为 $\varepsilon(\gcd(i,j))$($\varepsilon(n)$ 当且仅当 $n=1$ 时值为 $1$ 否则为 $0$ ),故原式化为
将 $\varepsilon$ 函数展开得到
变换求和顺序,先枚举 $d\mid gcd(i,j)$ 可得(其中 $[d\mid i]$ 表示 $i$ 是 $d$ 的倍数时对答案有 $1$ 的贡献)
易知 $1\sim\lfloor\frac{n}{k}\rfloor$ 中 $d$ 的倍数有 $\lfloor\frac{n}{kd}\rfloor$ 个,故原式化为
很显然,式子可以数论分块求解(过程中默认 $n\le m$)。
时间复杂度:$O(N+T\sqrt{n})$
Code
1 |
|