题解：P16098 [ICPC 2019 NAIPC] It' s a Mod, Mod, Mod, Mod World
_DEQUE_
·
·
题解
前言
一道类欧几里得算法的板子。
蒟蒻打算在此证明一下类欧几里得算法。
类欧几里得算法：
对于 T=5\times10^5，a,b,c,n\le10^9，求出 $\sum_{i=1}^n \lfloor\frac{ai+b}{c}\rfloor
我们设 $f(n,a,b,c)=\sum_{i=1}^n \lfloor\frac{ai+b}{c}\rfloor$，然后进行分类讨论：
#### 1.当 $a=0$ 时：
显然，$f(n,a,b,c)=n\times \lfloor \frac{b}{c} \rfloor
2.当 a\ge c 或 b\ge c 时：
f(n,a,b,c)=\sum_{i=1}^n \lfloor\frac{ai+b}{c}\rfloor
=\sum_{i=1}^n \lfloor \frac{(a \bmod c+c\lfloor \frac{a}{c}\rfloor)i+(b \bmod c+c\lfloor \frac{b}{c}\rfloor)}{c} \rfloor
=\sum_{i=1}^{n} \lfloor\lfloor \frac{a}{c} \rfloor i+\lfloor \frac{b}{c} \rfloor + \frac{(a \bmod c)i+(b \bmod c)}{c}\rfloor
由于前两项都是下取整，三项共同下取整，所以就等价于三项向下取整之和。
=\sum_{i=1}^{n} [ \lfloor \frac{a}{c} \rfloor i+\lfloor \frac{b}{c} \rfloor + \lfloor\frac{(a \bmod c)i+(b \bmod c)}{c}\rfloor]
然后把式子左右拆开：
=\sum_{i=1}^{n} (\lfloor \frac{a}{c} \rfloor i+\lfloor \frac{b}{c} \rfloor) +\sum_{i=1}^{n} \lfloor\frac{(a \bmod c)i+(b \bmod c)}{c}\rfloor
我们注意到右式 \sum_{i=1}^{n} \lfloor\frac{(a \bmod c)i+(b \bmod c)}{c}\rfloor = f(n,a\bmod c,b\bmod c,c)，左式可以直接计算。
于是我们就得到：
f(n,a,b,c)=\lfloor \frac{a}{c}\rfloor \times \frac{(n+1)\times n}{2} + \lfloor \frac{b}{c}\rfloor \times n + f(n,a\bmod c,b\bmod c,c)
至于为什么要取模操作，我们扔到后面说。
3.a\ne 0 且 a,b<c
最困难的一个。
f(n,a,b,c)=\sum_{i=1}^n \lfloor\frac{ai+b}{c}\rfloor
=\sum_{i=1}^{n} \sum_{j=0}^{\lfloor\frac{ai+b}{c}\rfloor-1} 1
这里我们将和式交换顺序：
=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1} \sum_{i=1}^{n} 1[j<\lfloor\frac{ai+b}{c}\rfloor]
我们定义 m=\lfloor\frac{an+b}{c}\rfloor，则
=\sum_{j=0}^{m-1} \sum_{i=1}^{n} 1[j<\lfloor\frac{ai+b}{c}\rfloor]
=\sum_{j=0}^{m-1} \sum_{i=1}^{n} 1[j+1\le\frac{ai+b}{c}]
=\sum_{j=0}^{m-1} \sum_{i=1}^{n} 1[cj+c\le ai+b]
=\sum_{j=0}^{m-1} \sum_{i=1}^{n} 1[cj+c-b\le ai]
=\sum_{j=0}^{m-1} \sum_{i=1}^{n} 1[cj+c-b-1<ai]
=\sum_{j=0}^{m-1} \sum_{i=1}^{n} 1[\frac{cj+c-b-1}{a}<i]
=\sum_{j=0}^{m-1} \frac{cj+c-b-1}{a}
欸这不就等于 f(m-1,c,c-b-1,a) 嘛！
那么我们就可以得出结论：
f(n,a,b,c)=\begin{cases}n\times \lfloor \frac{b}{c} \rfloor,a=1\\\lfloor \frac{a}{c}\rfloor \times \frac{(n+1)\times n}{2} + \lfloor \frac{b}{c}\rfloor \times n + f(n,a\bmod c,b\bmod c,c),a\ge c\text{ 或 }b\ge c\\f(m-1,c,c-b-1,a),a\ne 0 \text{ 且 } a,b<c\end{cases}
至于为什么要取模：
- 我们注意到 m=\lfloor\frac{an+b}{c}\rfloor，取模后我们才能保证 m<n，否则就可能会使得 m>n，导致你前面的操作都白干。
- 同时取模保证了时间复杂度。我们观察 a,c 的对应值：
取模操作：a_1 = a_0 \bmod c_0。
求值操作：a_2 = c_1,c_2=a_1。
换句话说就是先交换再取模。
然后我们惊人的发现，这和欧几里得算法求最大公因数惊人的相似。所以时间复杂度被保证在了 log 级别。
对应到此题中：
\sum_{i=1}^{n}(pi\bmod q)
=\sum_{i=1}^{n}(pi-q\times\lfloor \frac{pi}{q} \rfloor)
=(\sum_{i=1}^{n}pi)-(\sum_{i=1}^{n}q\times\lfloor \frac{pi}{q} \rfloor)
=p\times\frac{n\times(n+1)}{2}-q\times f(n,p,0,q)
然后就用上述方式递归计算即可。
代码：
#include <bits/stdc++.h>
#define int long long
#define F(i,j,k) for(int i=j;i<=k;i++)
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define Luogu return
#define _DEQUE_ 0
using namespace std;
//const int N=;
int f(int n,int a,int b,int c){
int m=(a*n+b)/c;
if(a==0){
return 0;
}
if(a>=c||b>=c){
return (a/c)*n*(n+1)/2+(b/c)*(n+1)+f(n,a%c,b%c,c);
}
return n*m-f(m-1,c,c-b-1,a);
}
void solve(){
int p,q,n;
cin>>p>>q>>n;
cout<<p*n*(n+1)/2-q*f(n,p,0,q)<<endl;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin>>T;
while(T--){
solve();
}
Luogu _DEQUE_;
}