BZOJ3529 [Sdoi2014]数表 莫比乌斯反演+线性筛+树状数组

发布于 2017-08-14  4.4k 次阅读


[toggle hide="yes" title="题目" color=""]

Description

有一张N×m的数表,其第i行第j列(1 < =i < =礼,1 < =j < =m)的数值为能同时整除i和j的所有自然数之和。给定a,计算数表中不大于a的数之和。

Input

输入包含多组数据。输入的第一行一个整数Q表示测试点内的数据组数,接下来Q行,每行三个整数n,m,a(|a| < =10^9)述一组数据。

Output

    对每组数据,输出一行一个整数,表示答案模2^31的值。

Sample Input

2
4 4 3
10 10 5

Sample Output

20
148

HINT

1 < =N.m < =10^5  , 1 < =Q < =2×10^4

[/toggle]

先不考虑a的限制,设S(i)表示i的约数和,$$f(x) = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^m {[\gcd (i,j) = = x]} } $$

 

首先考虑线性筛约数和,首先,由约数和定理

$$s(x) = \prod\limits_{i = 1} {(\sum\limits_{j = 0}^{{a_i}} {p_i^j} )} $$

可知,我们只需维护一个数的最小质因子对答案的贡献g(x),即可线性筛出约数和。

1.当i是质数时,g(i)=s(i)=i+1。

2.当i与p互质时,利用积性函数的性质。

3.当i不与p互质时,求s(i*p)只需将s(i)除去g(i)的贡献后,再乘上g(i*p)的贡献即可。

设不考虑a时,设h(x)为答案前缀和,推一推式子:

$$\eqalign{
& h(x) = f(x)S(x) \cr
& = \sum\limits_{d = 1}^n {S(d)} \sum\limits_{t = 1}^{\left\lfloor {{n \over t}} \right\rfloor } {\left\lfloor {{n \over {dt}}} \right\rfloor } \left\lfloor {{m \over {dt}}} \right\rfloor \mu (d) \cr
& = \sum\limits_{D = 1}^n {\left\lfloor {{n \over D}} \right\rfloor } \left\lfloor {{m \over D}} \right\rfloor \sum\limits_{t|D}^{} {S(t)\mu ({D \over t})} \cr} $$

 

最后,考虑限制a对答案的影响,显然枚举t之前的部分可以O(n^0.5)分块处理,而对于后一部分,可以利用离线|树状数组来搞。将询问按照a从小到大排序,将约数和s及其下标从小到大排序,每次插入所有s(t)小于a的部分(包括其倍数),然后差分就好了,具体实现见代码。

 

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974