辗转相除法的一个奇妙的题

题意

给定四个整数n, a, b, c,求
$$\sum_{x=1}^n\lfloor\frac{a\times x+b}{c}\rfloor$$

做法

首先,如果$a=p\times c+q$,其中$q=a模c$,那么$p$是可以从下取整符号中提取出来的,答案需要加上$p\times\frac{n(n+1)}{2}$。同理,$b=p\times c+q$时,答案需要加上$p\times n$。

因此,我们只需考虑$a=a模c$与$b=b模c$即可。接下来是一系列神奇的式子。设$k=\lfloor\frac{a\times n+b}{c}\rfloor$,则

$$
\sum_{x=1}^n\lfloor\frac{a\times x+b}{c}\rfloor
$$
$$

\sum_{x=1}^n\sum_{i=1}^k\mathbf{1}(i\le\lfloor\frac{a\times x+b}{c}\rfloor)
$$
$$

\sum_{i=1}^k\sum_{x=1}^n\mathbf{1}(x\ge\lceil\frac{i\times c-b}{a}\rceil)
$$
$$
=\sum_{i=1}^k(n-\lfloor\frac{i\times c - b - 1}{a}\rfloor)
$$

于是,$a$和$c$交换了位置,可以递归调用该函数。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def brute_force(n, a, b, c):
res = 0
for x in range(1, n + 1):
res += (a * x + b) // c
return res


def f(n, a, b, c):
if c == 0:
return 0
res = (a // c) * n * (n + 1) // 2 + (b // c) * n
a %= c
b %= c
k = (a * n + b) // c
return res + k * n - f(k, c, -b - 1, a)


n = 1001293
a = 123
b = 4564
c = 789
print(brute_force(n, a, b, c))
print(f(n, a, b, c))

输出为:

1
2
3
$ python3 temp.py
78153838770
78153838770

还要注意一点,python中的整除与C++中的不太一样。

Python中:

1
2
-5 // 2 = -3
-5 % 2 = 1

C++中:

1
2
-5 / 2 = -2
-5 % 2 = -1