第一种
f ( a , b , c , n ) = ∑ i = 0 n a i + b c f(a,b,c,n)=\sum_{i=0}^n\frac{ai+b}{c} f(a,b,c,n)=i=0∑n?cai+b?
情况一： a ≥ co rb ≥ c a\ge c~or~b \ge c a≥c or b≥c
f ( a , b , c , n ) = f ( a % c , b % c , c , n ) + n ( n + 1 ) 2 ? a c + b c ? ( n + 1 ) f(a,b,c,n)=f(a\%c,b\%c,c,n)+\frac{n(n+1)}{2}\cdot\frac{a}{c}+\frac{b}{c}\cdot(n+1) f(a,b,c,n)=f(a%c,b%c,c,n)+2n(n+1)??ca?+cb??(n+1)
情况二： a < ba n da < c a< b~and~a< c af ( a , b , c , n ) = ∑ i = 0 n ∑ j = 1 m [ a i + b ≥ c j ] = ( n + 1 ) m ? ∑ j = 0 m ? 1 c j + ( c ? b + a ? 1 ) a = ( n + 1 ) m ? f ( c , c ? b + a ? 1 , a , m ? 1 ) f(a,b,c,n)=\sum_{i=0}^n\sum_{j=1}^m[ai+b\ge cj]=(n+1)m-\sum_{j=0}^{m-1}\frac{cj+(c-b+a-1)}{a}=(n+1)m-f(c,c-b+a-1,a,m-1) f(a,b,c,n)=i=0∑n?j=1∑m?[ai+b≥cj]=(n+1)m?j=0∑m?1?acj+(c?b+a?1)?=(n+1)m?f(c,c?b+a?1,a,m?1)
第二种
【类欧几里得算法推导】 g ( a , b , c , n ) = ∑ i = 0 n i a i + b c g(a,b,c,n)=\sum_{i=0}^ni\frac{ai+b}{c} g(a,b,c,n)=i=0∑n?icai+b?
情况一： a ≥ co rb ≥ c a\ge c~or~b \ge c a≥c or b≥c
g ( a , b , c , n ) = g ( a % c , b % c , c , n ) + n ( n + 1 ) ( 2 n + 1 ) 6 ? a c + n ( n + 1 ) 2 ? b c g(a,b,c,n)=g(a\%c,b\%c,c,n)+\frac{n(n+1)(2n+1)}{6}\cdot\frac{a}{c}+\frac{n(n+1)}{2}\cdot\frac{b}{c} g(a,b,c,n)=g(a%c,b%c,c,n)+6n(n+1)(2n+1)??ca?+2n(n+1)??cb?
情况二： a < ba n da < c a< b~and~a< c ag ( a , b , c , n ) = ∑ i = 0 n i ∑ j = 1 m [ a i + b ≥ c j ] = g(a,b,c,n)=\sum_{i=0}^ni\sum_{j=1}^m[ai+b\ge cj]= g(a,b,c,n)=i=0∑n?ij=1∑m?[ai+b≥cj]=
1 2 ( m n ( n + 1 ) ? ∑ j = 0 m ? 1 ( c j + ( c ? b + a ? 1 ) a ) 2 + ∑ j = 0 m ? 1 c j + ( c ? b + a ? 1 ) a ) = \frac{1}{2}\left(mn(n+1)-\sum_{j=0}^{m-1}\left(\frac{cj+(c-b+a-1)}{a}\right)^2+\sum_{j=0}^{m-1}\frac{cj+(c-b+a-1)}{a}\right)= 21?(mn(n+1)?j=0∑m?1?(acj+(c?b+a?1)?)2+j=0∑m?1?acj+(c?b+a?1)?)=
1 2 ( m n ( n + 1 ) ? h ( c , c ? b + a ? 1 , a , m ? 1 ) + f ( c , c ? b + a ? 1 , a , m ? 1 ) ) \frac{1}{2}(mn(n+1)-h(c,c-b+a-1,a,m-1)+f(c,c-b+a-1,a,m-1)) 21?(mn(n+1)?h(c,c?b+a?1,a,m?1)+f(c,c?b+a?1,a,m?1))
第三种
h ( a , b , c , n ) = ∑ i = 0 n ( a i + b c ) 2 h(a,b,c,n)=\sum_{i=0}^n\left(\frac{ai+b}{c}\right)^2 h(a,b,c,n)=i=0∑n?(cai+b?)2
情况一： a ≥ co rb ≥ c a\ge c~or~b \ge c a≥c or b≥c
h ( a , b , c , n ) = n ( n + 1 ) ( 2 n + 1 ) 6 ? ( a c ) 2 + ( b c ) 2 ? ( n + 1 ) + a c ? b c n ( n + 1 ) + h(a,b,c,n)=\frac{n(n+1)(2n+1)}{6}\cdot\left(\frac{a}{c}\right)^2+\left(\frac{b}{c}\right)^2\cdot(n+1)+\frac{a}{c}\cdot\frac{b}{c}n(n+1)+ h(a,b,c,n)=6n(n+1)(2n+1)??(ca?)2+(cb?)2?(n+1)+ca??cb?n(n+1)+
2 a c g ( a % c , b % c , c , n ) + 2 b c f ( a % c , b % c , c , n ) + h ( a % c , b % c , c , n ) 2\frac{a}{c}g(a\%c,b\%c,c,n)+2\frac{b}{c}f(a\%c,b\%c,c,n)+h(a\%c,b\%c,c,n) 2ca?g(a%c,b%c,c,n)+2cb?f(a%c,b%c,c,n)+h(a%c,b%c,c,n)
情况二： a < ba n da < c a< b~and~a< c ah ( a , b , c , n ) = ∑ i = 0 n ∑ j = 1 m [ a i + b ≥ c j ] ( 2 j ? 1 ) = ∑ j = 0 m ? 1 ( 2 j + 1 ) ( n + 1 ? c j + ( c ? b + a ? 1 ) a ) = h(a,b,c,n)=\sum_{i=0}^n\sum_{j=1}^m[ai+b\ge cj](2j-1)=\sum_{j=0}^{m-1}(2j+1)\left(n+1-\frac{cj+(c-b+a-1)}{a}\right)= h(a,b,c,n)=i=0∑n?j=1∑m?[ai+b≥cj](2j?1)=j=0∑m?1?(2j+1)(n+1?acj+(c?b+a?1)?)=
m 2 ( n + 1 ) ? 2 g ( c , c ? b + a ? 1 , a , m ? 1 ) ? f ( c , c ? b + a ? 1 , a , m ? 1 ) m^2(n+1)-2g(c,c-b+a-1,a,m-1)-f(c,c-b+a-1,a,m-1) m2(n+1)?2g(c,c?b+a?1,a,m?1)?f(c,c?b+a?1,a,m?1)
大板子
洛谷P5170

#include using namespace std; typedef long long ll; ll modpow(ll a, int b); const int mod = 998244353, inv2 = (mod + 1) / 2, inv6 = modpow(6, mod - 2); ll modpow(ll a, int b) { ll res = 1; for (; b; b >>= 1) { if (b & 1) res = res * a % mod; a = a * a % mod; } return res; } struct Result { ll f, g, h; }; Result extgcd(ll a, ll b, ll c, ll n) { if (a == 0) return (Result) { b / c * (n + 1) % mod, n * (n + 1) / 2 % mod * (b / c) % mod, (b / c) * (b / c) % mod * (n + 1) % mod }; if (a >= c || b >= c) { Result lst = extgcd(a % c, b % c, c, n); ll ta = n * (n + 1) / 2 % mod, tb = n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod; ll ac = a / c, bc = b / c; return (Result) { (ta * ac + (n + 1) * bc + lst.f) % mod, (tb * ac + ta * bc + lst.g) % mod, (tb * ac % mod * ac + (n + 1) * bc % mod * bc + ta * 2 * ac % mod * bc + 2 * lst.g * (a / c) + 2 * lst.f * (b / c) + lst.h) % mod }; } ll m = (a * n + b) / c; Result lst = extgcd(c, c - b + a - 1, a, m - 1); return (Result) { ((n + 1) * m - lst.f + mod) % mod, (m * n % mod * (n + 1) + lst.f - lst.h + 2ll * mod) % mod * inv2 % mod, (m * m % mod * (n + 1) - 2 * lst.g - lst.f + 3ll * mod) % mod }; } int main() { int T, a, b, c, n; for (scanf("%d", &T); T--; ) { scanf("%d%d%d%d", &n, &a, &b, &c); Result res = extgcd(a, b, c, n); printf("%lld %lld %lld\n", res.f, res.h, res.g); } return 0; }