题解：P16098 [ICPC 2019 NAIPC] It' s a Mod, Mod, Mod, Mod World

huashao_139 · 2026-08-08 10:55:46 · 题解

发现 \displaystyle \sum_{i = 1}^n (ip \bmod q) = \displaystyle \sum_{i = 1}^n (ip - q\lfloor \frac{ip}q \rfloor) = \displaystyle \sum_{i = 1}^n ip - \displaystyle \sum_{i = 1}^n q\lfloor \frac{ip}q \rfloor = \frac{np (n + 1)}{2} - \displaystyle \sum_{i = 1}^n q\lfloor \frac{ip + 0}q \rfloor。

套用类欧几里德算法公式即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

inline int F (int a, int b, int c, int n)
{
    if (a == 0) return (b / c) * (n + 1);
    if (a >= c || b >= c) return F(a % c, b % c, c, n) + (b / c) * (n + 1) + (a / c) * n * (n + 1) / 2;
    int m = (a * n + b) / c; return n * m - F(c, c - b - 1, a, m - 1);
}

int p, q, n;
inline void solve()
{
    scanf("%lld %lld %lld", &p, &q, &n);
    printf("%lld\n", p * n * (n + 1) / 2 - q * F(p, 0, q, n));
}

int T;
signed main()
{
    scanf("%lld", &T);
    while (T--) solve();
    return 0;
}