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

123456wjc · 2026-05-12 12:37:40 · 题解

题意简述

给定 n,p,q，求解 \sum_{i=1}^{n} (pi \bmod q)。

做法简述

首先先简单的推式子。我们有取模变形的经典结论：a \bmod b = a - b \lfloor \frac{a}{b} \rfloor。那么原式等于：

那么我们再考虑拆求和式。利用类欧算法可以快速求解。

对于求和式 \sum_{i=0}^{n} \lfloor \frac{ai+b}{c} \rfloor，我们分两类讨论：

• 其他情况，我们交换求和顺序。

对于后一种情况，原式的意义是对每个 i 计数 y \le \lfloor \frac{ai+b}{c} \rfloor，我们变形为 i \ge \lceil \frac{cy-b}{a} \rceil = \lfloor \frac{cy+a-b-1}{a} \rfloor。之后，求和式变为 \sum_{y=1}^{m} n-\lfloor \frac{cy+a-b-1}{a} \rfloor+1 = m(n+1) - \sum_{y=1}^{m} \lfloor \frac{cy+a-b-1}{a} \rfloor。其中 m=\lfloor \frac{cn+a-b-1}{a} \rfloor。

我们考虑将求和范围统一为从 0 开始。原式变为：

这样，我们反复应用两种基本情形。因为这种操作很像辗转相除的过程，因此这被称为类欧几里得算法。时间复杂度可以证明为 \log 级别的。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int solve(int a,int b,int c,int n){
    if(!n) return b/c;
    if(!a) return b/c*(n+1);
    if(a>=c || b>=c){
        return solve(a%c,b%c,c,n)+(a/c)*(n)*(n+1)/2+(b/c)*(n+1);
    }
    int m=(a*n+b)/c;
    if(!m) return 0;
    return n*m-solve(c,c-b-1,a,m-1);
}
signed main(){
    int n;
    cin>>n;
    while(n--){
        int p,q,n;
        cin>>p>>q>>n;
        cout<<(p*(n+1)*(n)/2)-q*solve(p,0,q,n)<<'\n';
    }
}