经典题目
给你 a,b,c,n，求
∑i=1n⌊ax+bc⌋
方法：辗转相除法
推导如下：
∑x=1n⌊ax+bc⌋
=∑x=1n∑k=1[k≤ax+bc]
=∑k=1∑x=1n[k≤ax+bc]
注：[ ]表达式可视为布尔表达式，当括号内返回值为“真”时，表达式值为1，否则表达式的值为0。
下面化简 k≤ax+bc⇐⇒ck−b≤ax⇐⇒x≥⌈ck−ba⌉
⇐⇒x≥⌊ck−b+a−1a⌋
=∑k=1kmax=⌊an+bc⌋∑x=1n[x≥⌊kc−b+a−1a⌋]
=∑k=1kmax(n+1−⌊kc−b+a−1a⌋)
=kmax∗(n+1)−∑k=1kmax⌊ck−b+a−1a⌋
观察算式，前面
kmax∗(n+1)可以
O(1)算出来，而后面的
∑kmaxk=1⌊ck−b+a−1a⌋则转化为了原问题
∑nx=1⌊ax+bc⌋的子问题。
在这里有一个优化：
∑x=1n⌊ax+bc⌋
=∑x=1n⌊(a mod c+⌊ac⌋∗c)∗x+b mod c+⌊bc⌋∗cc⌋
=∑x=1n⌊a mod c∗x+b mod cc+⌊ac⌋∗x+⌊bc⌋⌋
=∑x=1n⌊a mod c∗x+b mod cc⌋+∑x=1n(⌊ac⌋∗x+⌊bc⌋)
∑x=1n⌊a mod c∗x+b mod cc⌋+⌊ac⌋∗n∗(n+1)2+⌊bc⌋∗n
现在，我们使得
a,b≤c，再用我们上面推得的公式，问题转化为它的子问题
∑kmaxk=1⌊ck−b+a−1a⌋，相当于
a,c交换位置，继续取模变小。这样一来我们每次交换、取模，直到
n≤0，相当于进行了一次
Gcd(a,c)，所以复杂度是
O(log2N)。问题得到完美解决。
总结：
从这道题中我们可以得到以下经验：
1. 当遇到一些问题时，我们可以将它转化为含有布尔表达式的算式，不要觉得布尔表达式难以解决，当我们以后使用莫比乌斯函数μ(x)可以方便的解决含有布尔表达式的算式
2. 注意向上取整⌈ ⌉与向下取整⌊ ⌋之间的互相转换：⌊x⌋=−⌈−x⌉,⌈x⌉=−⌊−x⌋,⌈ab⌉=⌊a+b−1b⌋
3. 要灵活掌握整除与取模的关系转换：a mod b=a−⌊ab⌋∗b
4. 要拥有将现有问题转化为同类型子问题的能力，从而迭代计算
5. 公式推导能力很重要，不然一切都是扯淡，233。。。
