BZOJ3529: [Sdoi2014]数表-布布扣-bubuko.com

Description

有一张 n×m 的数表，其第 i 行第 j 列（1 <= i <= n, 1 <= j <= m）的数值为能同时整除 i 和 j 的所有自然数之和。

给定 a , 计算数表中不大于 a 的数之和。

输入包含多组数据。

输入的第一行一个整数Q表示测试点内的数据组数

接下来Q行，每行三个整数n，m，a(|a| < =10^9)描述一组数据。

1 < =N．m < =10^5 ， 1 < =Q < =2×10^4

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

2
4 4 3
10 10 5

20
148

题解Here!

莫比乌斯反演的标准模板题。

首先，把那个$a$的约束与取模运算先丢一边去。

设$f(x)$为题目要求的约束和，即$f(x)=\sum_{d|x}d$。

那么题目要求的就是：$$\sum_{i=1}^n\sum_{j=1}^mf(gcd(i,j))$$

未完待续。。。

原文：https://www.cnblogs.com/Yangrui-Blog/p/9456617.html