bzoj 2301 [HAOI2011]Problem b

Posted by

题目链接

http://www.lydsy.com/JudgeOnline/problem.php?id=2301

题解

首先根据容斥原理,转化为求\(\sum_{i=1}^b\sum_{j=1}^d[gcd(i,j)=k]+\sum_{i=1}^{a-1}\sum_{j=1}^{c-1}[gcd(i,j)=k]\\-\sum_{i=1}^{a-1}\sum_{j=1}^d[gcd(i,j)=p]-\sum_{i=1}^b\sum_{j=1}^{c-1}[gcd(i,j)=p]\)

之后和bzoj 2818 Gcd类似,转化成求\(\sum_{i=1}^{\frac np}\sum_{j=1}^{\frac np}[gcd(i,j)=1]\)

但是时间复杂度不兼容,于是引入整除分块:

我们发现对于某一段连续的\(d\)\(\frac nd\)是相同的,我们可以求出莫比乌斯函数的前缀和,利用乘法分配律,分别对于每一个\(\frac nd\)\(\frac md\)都相同的块求解即可。

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注