前言：网上看了一下这个知识点，最基本的那个式子会了之后，自己推了剩下的两个式子，发现其实还是很好推的
前置公式：
$x < left lfloor frac{n}{y} ight floor Leftrightarrow x < left lceil frac{n-y+1}{y} ight ceil$
$x < left lceil frac{n}{y} ight ceil Leftrightarrow x * y < n$
$x * y > n Leftrightarrow x > left lfloor frac{n}{y} ight floor$
类欧几里得：
给定 $n$, $a$, $b$, $c$，求下列三个算式的值
$f(n, a, b, c) = sum_{i=0}^nleft lfloor frac{a*i+b}{c} ight floor$
$g(n, a, b, c) = sum_{i=0}^n i * left lfloor frac{a*i+b}{c} ight floor$
$h(n, a, b, c) = sum_{i=0}^n (left lfloor frac{a*i+b}{c} ight floor)^2$
本文中作如下约定：
$m=left lfloor frac{a*n+b}{c} ight floor$
求$f(n, a, b, c)$
$Case 1$:当$a geqslant c || b geqslant c$时 $$ egin{align*}f(n, a, b, c) &= sum_{i=0}^nleft lfloor frac{a*i+b}{c} ight floor \ &=sum_{i=0}^n(left lfloor frac{(a\%c)*i+(b\%c)}{c} ight floor + left lfloor frac{a}{c} ight floor*i + left lfloor frac{b}{c} ight floor ) \ &= sum_{i=0}^nleft lfloor frac{(a\%c)*i+(b\%c)}{c} ight floor + left lfloor frac{a}{c} ight floor sum_{i=0}^ni + left lfloor frac{b}{c} ight floor * (n + 1) \ &=f(n, a\%c, b\%c, c) + left lfloor frac{a}{c} ight floor * frac{n*(n+1)}{2} + left lfloor frac{b}{c} ight floor * (n + 1) end{align*}$$
$Case 2$:当$a < c && b < c && a eq 0$时 $$egin{align*}f(n, a, b, c) &= sum_{i=0}^nleft lfloor frac{a*i+b}{c} ight floor \ &=sum_{i=0}^n sum_{j=0}^{left lfloor frac{a*i+b}{c} ight floor - 1}1 \ &=sum_{j=0}^{m-1} sum_{i=0}^n[j<left lfloor frac{a*i+b}{c} ight floor] \ &= sum_{j=0}^{m-1}sum_{i=0}^n[j<left lceil frac{a*i+b-c+1}{c} ight ceil] \ &= sum_{j=0}^{m-1}sum_{i=0}^n[c*j < a*i+b-c+1] \&= sum_{j=0}^{m-1}sum_{i=0}^n[a*i > c*j-b+c-1] \ &=sum_{j=0}^{m-1} sum_{i=0}^n[i>left lfloor frac{c*j-b+c-1}{a} ight floor] \ &= sum_{j=0}^{m-1}(n-left lfloor frac{c*j-b+c-1}{a} ight floor)\ &= n*m-f(m-1,c,-b+c-1,a)end{align*}$$
$Case 3$:当$a < c && b < c && a = 0$时 $$f(n, a, b, c) = 0$$
记$A(j)=left lfloor frac{c*j-b+c-1}{a} ight floor$
下面推导过程中与上面相似的步骤会省略
求$g(n, a, b, c)$
$Case 1$:当$a geqslant c || b geqslant c$时 $$ egin{align*}g(n, a, b, c)&= sum_{i=0}^n i*left lfloor frac{a*i+b}{c} ight floor \ &=sum_{i=0}^n(i*left lfloor frac{(a\%c)*i+(b\%c)}{c} ight floor + left lfloor frac{a}{c} ight floor*i^2 + left lfloor frac{b}{c} ight floor * i ) \ &= sum_{i=0}^n i * left lfloor frac{(a\%c)*i+(b\%c)}{c} ight floor + left lfloor frac{a}{c} ight floor sum_{i=0}^n i^2 + left lfloor frac{b}{c} ight floor sum_{i=0}^n i \ &=g(n, a\%c, b\%c, c) + left lfloor frac{a}{c} ight floor * frac{n*(n+1)*(2n+1)}{6} + left lfloor frac{b}{c} ight floor * frac{n*(n+1)}{2}end{align*} $$
$Case 2$:当$a < c && b < c && a eq 0$时 $$ egin{align*}g(n, a, b, c) &= sum_{i=0}^ni*left lfloor frac{a*i+b}{c} ight floor \ &=sum_{i=0}^n sum_{j=0}^{left lfloor frac{a*i+b}{c} ight floor - 1}i \ &=sum_{j=0}^{m-1} sum_{i=0}^ni*[j<left lfloor frac{a*i+b}{c} ight floor] \ &=sum_{j=0}^{m-1} sum_{i=0}^ni*[i>left lfloor frac{c*j-b+c-1}{a} ight floor] \ &= sum_{j=0}^{m-1}(frac{n*(n+1)}{2} -frac{A(j)*(A(j)+1)}{2})\ &= frac{m*n*(n+1)}{2}- frac{1}{2}sum_{j=0}^{m-1}(A(j))^2- frac{1}{2}sum_{j=0}^{m-1}A(j)\ &=frac{m*n*(n+1)}{2}-frac{1}{2}h(m-1, c, -b+c-1,a)-frac{1}{2}f(m-1, c,-b+c-1, a)end{align*}$$
$Case 3$:当$a < c && b < c && a = 0$时 $$g(n, a, b, c) = 0$$
求$h(n, a, b, c)$
$Case 1$:当$a geqslant c || b geqslant c$时 $$egin{align*}h(n, a, b, c) &= sum_{i=0}^n(left lfloor frac{a*i+b}{c} ight floor)^2 \ &=sum_{i=0}^n(left lfloor frac{(a\%c)*i+(b\%c)}{c} ight floor + left lfloor frac{a}{c} ight floor*i + left lfloor frac{b}{c} ight floor )^2 \ &= sum_{i=0}^n(left lfloor frac{(a\%c)*i+(b\%c)}{c} ight floor)^2 +2left lfloor frac{a}{c} ight floorsum_{i=0}^ni left lfloor frac{(a\%c)*i+(b\%c)}{c} ight floor +2left lfloor frac{b}{c} ight floorsum_{i=0}^n left lfloor frac{(a\%c)*i+(b\%c)}{c} ight floor+ (left lfloor frac{a}{c} ight floor)^2 sum_{i=0}^ni^2 + (left lfloor frac{b}{c} ight floor)^2 *(n+1)+2left lfloor frac{a}{c} ight floorleft lfloor frac{b}{c} ight floor sum_{i=0}^ni \ &= h(n, a\%c, b\%c, c)+2left lfloor frac{a}{c} ight floor g(n,a\%c, b\%c, c)+2left lfloor frac{b}{c} ight floor f(n, a\%c, b\%c, c)+(left lfloor frac{a}{c} ight floor)^2*frac{n*(n+1)*(2n+1)}{6}+ (left lfloor frac{b}{c} ight floor)^2 *(n+1)+2left lfloor frac{a}{c} ight floorleft lfloor frac{b}{c} ight floor*frac{n*(n+1)}{2}end{align*}$$
$Case 2$:当$a<c && b<c && a eq 0$时 $$egin{align*}h(n,a,b,c) &=sum_{i=0}^n(left lfloor frac{a*i+b}{c} ight floor)^2\ &=sum_{i=0}^n sum_{j=0}^{left lfloor frac{a*i+b}{c} ight floor -1}sum_{k=0}^{left lfloor frac{a*i+b}{c} ight floor -1}1\ &=sum_{j=0}^{m-1}sum_{k=0}^{m-1}sum_{i=0}^n[j<left lfloor frac{a*i+b}{c} ight floor&&k<left lfloor frac{a*i+b}{c} ight floor]\ &=sum_{j=0}^{m-1}sum_{k=0}^{m-1}sum_{i=0}^n[i>A(j)&&i>A(k))]\ &= sum_{j=0}^{m-1}sum_{k=0}^{m-1}sum_{i=0}^n[i>A(max(j,k))]\ &=2sum_{j=0}^{m-1}sum_{k=0}^{j-1}sum_{i=0}^n[i>A(j)] +sum_{j=0}^{m-1}sum_{i=0}^n[i>A(j)]\ &= 2sum_{j=0}^{m-1}j*(n-A(j))+sum_{j=0}^{m-1} (n-A(j))\ &=2nsum_{j=0}^{m-1}j-2sum_{j=0}^{m-1}j*A(j)+m*n-sum_{j=0}^{m-1}A(j)\ &=2n*frac{(m-1)*m}{2}+m*n-2g(m-1, c,-b+c-1,a)-f(m-1,c,-b+c-1,a)\ &=n*m^2-2g(m-1, c,-b+c-1,a)-f(m-1,c,-b+c-1,a)end{align*}$$
$Case 3$:当$a < c && b < c && a = 0$时 $$h(n, a, b, c) = 0$$
代码：(洛谷P5170)
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; typedef long long ll; const int mod = 998244353; inline int read() { int ret, f=1; char c; while((c=getchar())&&(c<'0'||c>'9'))if(c=='-')f=-1; ret=c-'0'; while((c=getchar())&&(c>='0'&&c<='9'))ret=(ret<<3)+(ret<<1)+c-'0'; return ret*f; } int T, n, inv2, inv6; struct node{ ll fir, sec, thr; node(){} node(ll x, ll y, ll z) { fir = x; sec = y; thr = z; } }ans; ll add(ll x, ll y) { return x + y < mod? x + y: x + y - mod; } ll rdc(ll x, ll y) { return x - y < 0? x - y + mod: x - y; } ll qpow(ll x, int y) { ll ret = 1; while(y) { if(y&1) ret = ret * x % mod; x = x * x % mod; y >>= 1; } return ret; } ll calc1(ll x) { return (x * (x + 1) % mod) * inv2 % mod; } ll calc2(ll x) { return ((x * (x + 1) % mod) * (2 * x + 1) % mod) * inv6 % mod; } node dfs(ll x, ll a, ll b, ll c) { if(x < 0) return node(0, 0, 0); if(a >= c || b >= c) { node ret, res = dfs(x, a % c, b % c, c); ret.fir = (a / c) * calc1(x) % mod; ret.fir = add(ret.fir, (x + 1) * (b / c) % mod); ret.fir = add(ret.fir, res.fir); ret.sec = add((a / c) * calc2(x) % mod, (b / c) * calc1(x) % mod); ret.sec = add(ret.sec, res.sec); ret.thr = res.thr; ret.thr = add(ret.thr, (2 * (a / c) % mod) * res.sec % mod); ret.thr = add(ret.thr, (2 * (b / c) % mod) * res.fir % mod); ret.thr = add(ret.thr, (2 * (a / c) * (b / c) % mod) * calc1(x) % mod); ret.thr = add(ret.thr, ((a / c) * (a / c) % mod) * calc2(x) % mod); ret.thr = add(ret.thr, ((b / c) * (b / c) % mod) * (x + 1) % mod); return ret; } if(a == 0 || x == 0) return node(0, 0, 0); ll m = (a * x + b) / c; node res = dfs(m - 1, c, - b + c - 1, a), ret; ret.fir = rdc(m * x % mod, res.fir); ret.sec = add(res.thr, res.fir); ret.sec = ret.sec * inv2 % mod; ret.sec = rdc(m * calc1(x) % mod, ret.sec); ret.thr = (x * m % mod) * m % mod; ret.thr = rdc(ret.thr, add(2 * res.sec % mod, res.fir)); return ret; } int main() { T = read(); int a, b, c; inv2 = (mod + 1) >> 1; inv6 = qpow(6, mod - 2); while(T --) { n = read(); a = read(); b = read(); c = read(); ans = dfs(n, a, b, c); printf("%lld %lld %lld ", ans.fir, ans.thr, ans.sec); } return 0; }