题意
给定四个整数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 | def brute_force(n, a, b, c): |
输出为:
1 | $ python3 temp.py |
还要注意一点,python中的整除与C++中的不太一样。
Python中:
1 | -5 // 2 = -3 |
C++中:
1 | -5 / 2 = -2 |