OiClass P2688 简单计算题解

思路

我们简单导一下柿子：

\[ \begin{align*} \sum_{i=0}^{p} \left\lfloor\frac{iq}{p}\right\rfloor &= \left\lfloor\frac{0q}{p}\right\rfloor + \left\lfloor\frac{1q}{p}\right\rfloor + \cdots + \left\lfloor\frac{pq}{p}\right\rfloor \newline &= \frac{0q}{p} - \frac{0q\,\%\,p}{p} + \frac{1q}{p} - \frac{1q\,\%\,p}{p} + \cdots + \frac{pq}{p} - \frac{pq\,\%\,p}{p} \newline &= \frac{\frac{(p + 1)(0 + pq)}{2}}{p} -\frac{0q\,\%\,p + 1q\,\%\,p + \cdots+ pq\,\%\,p}{p}\newline &= \frac{(p + 1)q}{2} - \frac{0q\,\%\,p + 1q\,\%\,p + \cdots+ pq\,\%\,p}{p}\newline \end{align*} \]

然后发现导不出来了，尝试找规律。设 \(p = 6\)，\(q=4\)。则：

\[ \begin{align*} 原式&=\frac{(6+1)\times 4}{2} - \frac{0\,\%\,6 + 4\,\%\,6+8\,\%\,6+12\,\%\,6+16\,\%\,6+20\,\%\,6+24\,\%\,6}{6}\newline &=14-\frac{0+4+2+0+4+2+0}{6} \end{align*} \]

似乎存在一个循环节，长度为 \(2\)，猜一下循环节的长度就是 \(\frac{p}{(p,\,q)} = 3\)【\((a,\,b)\) 为 \(a\)、\(b\) 的最大公因数】。然后我们把序列倒着读，就像这样：

\[ 0,\,2,\,4,\,0,\,2,\,4,\,0 \]

我们会发现，舍弃最后一个 \(0\) 之后，数列就是 \((p,\,q)\) 个长度为 \(\frac{p}{(p,\,q)}\)，公差为 \((p,\,q)\) 的等差数列。

于是我们可以如此化简：

\[ 设\,\, d = (p,\,q)\,,\,l=\frac{p}{d}\,\, 则:\newline \begin{align*} 原式&= \frac{(p +1)q}{2} - \frac{d \left(\frac{l(0 + d\left(l - 1\right))}{2}\right)}{p} \end{align*} \]

然后简单实现一下即可。

代码

#include <iostream>
#include <algorithm>

#define int long long
#define endl '\n'

using namespace std;

int n, p, q;

signed main() {
    cin >> n;
    while (n--) {
        cin >> p >> q;
        int d = __gcd(p, q);
        int l = p / __gcd(p, q);
        int a = (d * (l - 1LL)) * l / 2LL;
        int ans = (p + 1LL) * q / 2LL - d * a / p;
        cout << ans << endl;
    }
}