【BZOJ3529】【SDOI2014】 数表

Time Limit: 10 Sec Memory Limit: 512 MB

Description

​ 有一张\(n×m\)的数表,其第i行第j列(\(,1 \le i \leq n,1 \le j \le 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 \le n,m \le 10^5 \\ 1 \le Q \le 2×10^4\)

Solution

​ 先忽略\(a\)的条件。

​ 令\(f(n)\)表示\(n\)的所有约数之和, \(sum(x)\)表示\(且x=gcd(i,j),1\le i \le n且1\le j \le m\)的数对数量.

​ 按照之前的反演,\(sum(x)=\sum\limits_{x|d}\mu(\frac dx)\lfloor\frac nd\rfloor\lfloor\frac md\rfloor=\sum\)
\[
\begin{aligned}
ans&=\sum_{i=1}^n\sum_{j=1}^m\sum_{d|i且d|j}d\\
&=\sum_{i=1}^n\sum_{j=1}^mf(gcd(i,j))\\
&=\sum_{d=1}^{min(n,m)}f(d)sum(d)\\
&=\sum_{d=1}^{min(n,m)}f(d)\sum_{x|d}\mu(\frac dx)\lfloor\frac nd\rfloor\lfloor\frac md\rfloor\\
&=\sum_{d=1}^{min(n,m)}f(d)\sum_{k=1}^{\lfloor min(n,m)/d\rfloor}\mu(\frac {kx}x)\lfloor\frac n{kx}\rfloor\lfloor\frac m{kx}\rfloor\\
&=\sum_{T=1}^{min(n,m)}\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor\sum_{d|T}f(d)\mu(\frac Td)\\
&=\sum_{T=1}^{min(n,m)}\lfloor\frac nT\rfloor\lfloor\frac mT\rfloor g(T) &令g(x)=\sum_{d|x}f(d)\mu(\frac xd)
\end{aligned}
\]

​ 其实\(g(x)\)是可以暴力求解的...因为\(x\)的因数个数不是很多。但是我们不能直接算完,因为有\(a\)的限制。由此要引入树状数组。

​ 回头看\(a\)的条件,从第三行等式来看,只有\(d\leq a\)的\(f(d)\)才能有贡献。

​ 我们用一个树状数组来维护\(g(x)\)的前缀和,那么对于询问,按照\(a\)排序,将所有\(x\le a\)的\(f(x)\),枚举\(x|y\)的\(y\),更新\(g(y)+=f(x)\mu(\frac yx)\)。

​ 这样按照分块的套路求解\(ans\)即可.

f函数求解

​ \(f(x)=\sum\limits_{d|x}d\)

​ \(f(x)\)是积性函数,可以用线性筛求解:

​ (1) \(x\)是质数时,\(f(x)=1+x\)

​ (2)循环\(i\)与\(p\)筛到\(x\), \(x\)=\(p*i\).

​ 若\(i\nmid p\),则\(i\)与\(p\)互质,那么\(f(x)=f(i)f(p)=f(i)*(p+1)\).

​ 若\(i|p\),记\(i\)去除所有\(p\)因子后的数为\(a\). 则\(f(x)=f(i)*p+f(a)\).

​ 记\(i=p_1^{q_1}p_2^{q_2}...p_k^{q_k}\),则\(x=p_1^{q_1}p_2^{q_2}...p_{loc}^{q_{loc}+1}...p_k^{q_k}\),\(a=p_1^{q_1}..p_{loc-1}^{q_{loc-1}}p_{loc+1}^{q_{loc}+1}...p_k^{q_k}\).不严谨地,这里\(p_{loc}\)和\(q_{loc}\)分别代表的是\(p\),与\(p\)在质因数分解中的指数。
\[
\begin{aligned}
f(i)*p&=(1+p1+...+p1^{q1})...(1+p_{loc}+...+p_{loc}^{q_{loc}})...(1+p_k+...+p_k^{q_k})*p\\
&=(p_{loc}+p_{loc}^2+..+p_{loc}^{q_{loc}+1})f(a)\\
\therefore f(i)*p&+f(a)=(1+p_{loc}+p_{loc}^2+...+p_{loc}^{q_{loc}+1})f(a)=f(x)
\end{aligned}
\]

上一篇:高版本的jdk编译过的项目移到低版本的JDK的eclipse中出错的问题


下一篇:C#中怎么判断一个数组中是否存在某个数组值