题意

给三个数 N, A and B.(1<=N<=1000000000, 1<=A,B<=100000). 求 Σ| n%A - n%B | （n=0至N-1）

思路+详解

N太大，如果直接暴力求和，肯定超时。所以肯定要用比较巧妙的方法。

（以下的例子都是 A比B小）

例一

我们先来考虑一对互质的 A1=2 和 B1=3，它们的最小公倍数是A*B=6，现在我们看下面的表格：

我们把 0 到 5 放入了表格中

【表1】A1=2

余数	0	1
	0	1
	2	3
	4	5

【表2】B1=3

余数	0	1	2
	[ 0	1 ]	[ 2
	3 ]	[ 4	5]

根据【表1】 我们人为的把【表2】分为3组，这3组分别是【表1】里面的3排 [0 1]、[2 3]、[4 5]，同时我们也可以看见这3组分别的第一个元素在【表2】中的余数各不相同。
我们开一个大小为B1的数组 num。

【表3】
（注1：组的第一个元素 对B取模 是数组的下标）
（注2：值为 Σ| n%A - n%B | n取对应组中的所有元素 ）

数组元素	组	值Σ｜n%A-n%B｜	公式	公式应用范围	备注
num[0]	[0 1]	0	0	数组下标为0
num[1]	[4 5]	2*1 =2	A * 数组下标	数组下标从1到（B-A）
num[2]	[2 3]	1*2 + (3-2)*1=3	(A-k)*数组下标 +（B-数组下标）*k	数组下标从（B-A+1）到结束	这里的k从1开始累加

例二

现在我们在来看一对不互质的情况，我们都知道不互质的数在除以他们的最大公约数之后就互质了，我们令A2=6，B2=9,，这里A和B的值恰好是上面A1 B1的3倍，也就是说A2 B2的最大公约数是3，最小公倍数是18，现在我们看下面的2个表格：

我们把 0 到 17 放入了表格中

余数(A2=6)	0	1	2	3	4	5
	0	1	2	3	4	5
	6	7	8	9	10	11
	12	13	14	15	16	17

余数 (B2=9)	0	1	2	3	4	5	6	7	8
	[ 0	1	2	3	4	5 ]	[ 6	7	8
	9	10	11]	[12	13	14	15	16	17]

你会发现这里的每一组的值等于【例一】中对应组的值 乘以 3（3是他们的最大公约数）的平方：

[0    1    2    3    4    5]的值为    0
[6    7    8    9   10  11] 的值为    【例一】中 [2 3]的值乘以 3^2  = 27
[12  13  14  15  16  17]     的值为    【例一】中 [4 5]的值乘以 3^2 = 18  

有了上面的分析，现在我们只要2次求商取余，再将剩余部分直接统计，即可得答案。
此外，很多中间过程会超int，最好都long long 吧，本人被坑了很久。

　

　

---

版权声明

本文首发于 贺智超的博客（http://hezhichao.cn/ or http://hzc199307.github.io），转载请注明出处。

本文链接：http://hezhichao.cn/acm/solution_report/hdoj4611/
永久链接：http://hzc199307.github.io/acm/solution_report/hdoj4611/