类欧几里得

设三个函数 f ( a , b , c , n ) = ∑ i = 0 n a × i + b c , g ( a , b , c , n ) = ∑ i = 0 n i × a × i + b c , h ( a , b , c , n ) = ∑ i = 0 n ( a × i + b c ) 2 f(a, b, c, n) = \sum\limits_{i = 0} ^{n} \frac{a \times i + b}{c}, g(a, b, c, n) = \sum\limits_{i = 0} ^{n} i \times \frac{a \times i + b}{c}, h(a, b, c, n) = \sum\limits_{i = 0} ^{n} \left(\frac{a \times i + b}{c} \right) ^ 2 f(a,b,c,n)=i=0∑n​ca×i+b​,g(a,b,c,n)=i=0∑n​i×ca×i+b​,h(a,b,c,n)=i=0∑n​(ca×i+b​)2。

f ( a , b , c , n ) = ∑ i = 0 n ⌊ a × i + b c ⌋ , ( 0 ≤ a , b , c , n ) f(a, b, c, n) = \sum\limits_{i = 0} ^{n} \lfloor \frac{a \times i + b}{c} \rfloor, (0 \le a, b, c, n) f(a,b,c,n)=i=0∑n​⌊ca×i+b​⌋,(0≤a,b,c,n)

下面除法均为向下取整：

b ≥ c b \ge c b≥c

设 b ′ = b − b c × c b' = b - \frac{b}{c} \times c b′=b−cb​×c：
f ( a , b , c , n ) = ∑ i = 0 n a × i + b ′ c + b c = b c × n + ∑ i = 0 n a × i + b ′ c = b c × n + f ( a , b ′ , c , n ) f(a, b, c, n) = \sum_{i = 0} ^{n} \frac{a \times i + b'}{c} + \frac{b}{c}\\ = \frac{b}{c} \times n + \sum_{i = 0} ^{n} \frac{a \times i + b'}{c}\\ = \frac{b}{c} \times n + f(a, b', c, n) f(a,b,c,n)=i=0∑n​ca×i+b′​+cb​=cb​×n+i=0∑n​ca×i+b′​=cb​×n+f(a,b′,c,n)

a ≥ c a \ge c a≥c

设 a ′ = a − a c × c a' = a - \frac{a}{c} \times c a′=a−ca​×c：
f ( a , b , c , n ) = ∑ i = 0 n a ′ × i + b c + a c × i = a c × n × ( n + 1 ) 2 + ∑ i = 0 n a ′ × i + b c = a c × n × ( n + 1 ) 2 + f ( a ′ , b , c , n ) f(a, b, c, n) = \sum_{i = 0} ^{n} \frac{a' \times i + b}{c} + \frac{a}{c} \times i\\ = \frac{a}{c} \times \frac{n \times (n + 1)}{2} + \sum_{i = 0} ^{n} \frac{a' \times i + b}{c}\\ = \frac{a}{c} \times \frac{n \times (n + 1)}{2} + f(a', b, c, n)\\ f(a,b,c,n)=i=0∑n​ca′×i+b​+ca​×i=ca​×2n×(n+1)​+i=0∑n​ca′×i+b​=ca​×2n×(n+1)​+f(a′,b,c,n)

综上，如果 a ≥ c ,   b ≥ c a \ge c,\ b \ge c a≥c, b≥c：
f ( a , b , c , n ) = f ( a ′ , b ′ , c , n ) + b c × n + a c × n × ( n + 1 ) 2 f(a, b, c, n) = f(a', b', c, n) + \frac{b}{c} \times n + \frac{a}{c} \times \frac{n \times (n + 1)}{2} f(a,b,c,n)=f(a′,b′,c,n)+cb​×n+ca​×2n×(n+1)​

考虑 a < c ,   b < c a < c,\ b < c a<c, b<c：
∑ i = 0 n a × i + b c ∑ i = 0 n ∑ j = 1 a × i + b c 1 \sum_{i = 0} ^{n} \frac{a \times i + b}{c}\\ \sum_{i = 0} ^{n} \sum_{j = 1} ^{\frac{a \times i + b}{c}}1\\ i=0∑n​ca×i+b​i=0∑n​j=1∑ca×i+b​​1
令 m = a × n + b c m = \frac{a \times n + b}{c} m=ca×n+b​，
∑ i = 0 n ∑ j = 1 m [ a × i + b c ≥ j ] ∑ i = 0 n ∑ j = 0 m − 1 [ a × i + b c ≥ j + 1 ] ∑ i = 0 n ∑ j = 0 m − 1 [ a × i + b ≥ j c + c ] ∑ i = 0 n ∑ j = 0 m − 1 [ a × i ≥ j c + c − b ] ∑ i = 0 n ∑ j = 0 m − 1 [ a × i > j c + c − b − 1 ] ∑ i = 0 n ∑ j = 0 m − 1 [ i > j c + c − b − 1 ] a ∑ j = 0 m − 1 ∑ i = 0 n [ i > j c + c − b − 1 ] a ∑ j = 0 m − 1 n − j c + c − b − 1 a n × m − ∑ i = 0 m − 1 i c + c − b − 1 a \sum_{i = 0} ^{n} \sum_{j = 1} ^{m} [\frac{a \times i + b}{c} \ge j]\\ \sum_{i = 0} ^{n} \sum_{j = 0} ^{m - 1}[\frac{a \times i + b}{c} \ge j + 1]\\ \sum_{i = 0} ^{n} \sum_{j = 0} ^{m - 1}[a \times i + b \ge jc + c]\\ \sum_{i = 0} ^{n} \sum_{j = 0} ^{m - 1}[a \times i \ge jc + c - b]\\ \sum_{i = 0} ^{n} \sum_{j = 0} ^{m - 1}[a \times i > jc + c - b - 1]\\ \sum_{i = 0} ^{n} \sum_{j = 0} ^{m - 1}[i > \frac{jc + c - b - 1]}{a}\\ \sum_{j = 0} ^{m - 1} \sum_{i = 0} ^{n}[i > \frac{jc + c - b - 1]}{a}\\ \sum_{j = 0} ^{m - 1} n - \frac{jc + c - b - 1}{a}\\ n \times m - \sum_{i = 0} ^{m - 1} \frac{ic + c - b - 1}{a}\\ i=0∑n​j=1∑m​[ca×i+b​≥j]i=0∑n​j=0∑m−1​[ca×i+b​≥j+1]i=0∑n​j=0∑m−1​[a×i+b≥jc+c]i=0∑n​j=0∑m−1​[a×i≥jc+c−b]i=0∑n​j=0∑m−1​[a×i>jc+c−b−1]i=0∑n​j=0∑m−1​[i>ajc+c−b−1]​j=0∑m−1​i=0∑n​[i>ajc+c−b−1]​j=0∑m−1​n−ajc+c−b−1​n×m−i=0∑m−1​aic+c−b−1​
a ′ = c , b ′ = c − b − 1 , c ′ = a a' = c, b' = c - b - 1, c' = a a′=c,b′=c−b−1,c′=a， f ( a , b , c , n ) = n × m − f ( a ′ , b ′ , c ′ , m − 1 ) f(a, b, c, n) = n \times m - f(a', b', c', m - 1) f(a,b,c,n)=n×m−f(a′,b′,c′,m−1)。

过程中 a = a % c , c = a a = a \% c, c = a a=a%c,c=a，发现跟 gcd ⁡ \gcd gcd的求解过程是一样的，最后 a a a会变成 0 0 0，也就是递归出口。

long long f(long long a, long long b, long long c, long long n) {
  if (!a) {
    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;
  }
  long long m = (a * n + b) / c;
  return n * m - f(c, c - b - 1, a, m - 1);
}

g ( a , b , c , n ) = ∑ i = 0 n i × a × i + b c , ( 0 ≤ a , b , c , n ) g(a, b, c, n) = \sum\limits_{i = 0} ^{n} i \times \frac{a \times i + b}{c}, (0 \le a, b, c, n) g(a,b,c,n)=i=0∑n​i×ca×i+b​,(0≤a,b,c,n)

b ≥ c , b ′ = b   %   c , d = b c b \ge c, b' = b\ \%\ c, d = \frac{b}{c} b≥c,b′=b % c,d=cb​:
∑ i = 0 n i × a × i + b ′ c + d × i d × n × ( n + 1 ) 2 + ∑ i = 0 n i × a × i + b ′ c g ( a , b , c , n ) = d × n × ( n + 1 ) 2 + g ( a , b ′ , c , n ) \sum_{i = 0} ^{n} i \times \frac{a \times i + b'}{c} + d \times i\\ d \times \frac{n \times (n + 1)}{2} + \sum_{i = 0} ^{n} i \times \frac{a \times i + b'}{c}\\ g(a, b, c, n) = d \times \frac{n \times (n + 1)}{2} + g(a, b', c, n)\\ i=0∑n​i×ca×i+b′​+d×id×2n×(n+1)​+i=0∑n​i×ca×i+b′​g(a,b,c,n)=d×2n×(n+1)​+g(a,b′,c,n)
a ≥ c , a ′ = a   %   c , d = a c a \ge c, a' = a\ \%\ c, d = \frac{a}{c} a≥c,a′=a % c,d=ca​：
∑ i = 0 n i × a ′ × i + b c + d × i 2 d × n × ( n + 1 ) × ( 2 n + 1 ) 6 + ∑ i = 0 n i × a ′ × i + b c d × n × ( n + 1 ) × ( 2 n + 1 ) 6 + g ( a ′ , b , c , n ) \sum_{i = 0} ^{n} i \times \frac{a' \times i + b}{c} + d \times i ^ 2\\ d \times \frac{n \times (n + 1) \times (2n + 1)}{6} + \sum_{i = 0} ^{n} i \times \frac{a' \times i + b}{c}\\ d \times \frac{n \times (n + 1) \times (2 n + 1)}{6} + g(a', b, c, n)\\ i=0∑n​i×ca′×i+b​+d×i2d×6n×(n+1)×(2n+1)​+i=0∑n​i×ca′×i+b​d×6n×(n+1)×(2n+1)​+g(a′,b,c,n)
综上， a ≥ c ,   b ≥ c a \ge c, \ b \ge c a≥c, b≥c：
g ( a , b , c , n ) = b c × n × ( n + 1 ) 2 + a c × n × ( n + 1 ) × ( 2 n + 1 ) 6 + g ( a ′ , b ′ , c , n ) g(a, b, c, n) = \frac{b}{c} \times \frac{n \times (n + 1)}{2} + \frac{a}{c} \times \frac{n \times (n + 1) \times (2n + 1)}{6} + g(a', b', c, n)\\ g(a,b,c,n)=cb​×2n×(n+1)​+ca​×6n×(n+1)×(2n+1)​+g(a′,b′,c,n)

a < c , b < c , m = a × n + b c , a ′ = c , b ′ = c − b − 1 , c ′ = a a < c, b < c, m = \frac{a \times n + b}{c}, a' = c, b' = c - b - 1, c'= a a<c,b<c,m=ca×n+b​,a′=c,b′=c−b−1,c′=a：
∑ i = 0 n i × ∑ j = 1 a × i + b c 1 ∑ i = 0 n i × ∑ j = 1 m [ a × i + b c ≥ j ] ∑ i = 0 n i × ∑ j = 0 m − 1 [ a × i + b c ≥ j + 1 ] ∑ i = 0 n i × ∑ j = 0 m − 1 [ i > j c + c − b − 1 a ] ∑ j = 0 m − 1 ∑ i = 0 n i [ i > j c + c − b − 1 a ] c a l c ( n ) = n × ( n + 1 ) 2 ∑ j = 0 m − 1 c a l c ( n ) − c a l c ( j c + c − b − 1 a ) m × n × ( n + 1 ) − f ( a ′ , b ′ , c ′ , m − 1 ) − h ( a ′ , b ′ , c ′ , m − 1 ) 2 \sum_{i = 0} ^{n} i \times \sum_{j = 1} ^{\frac{a \times i + b}{c}}1\\ \sum_{i = 0} ^{n} i \times \sum_{j = 1} ^{m} [\frac{a \times i + b}{c} \ge j]\\ \sum_{i = 0} ^{n} i \times \sum_{j = 0} ^{m - 1} [\frac{a \times i + b}{c} \ge j + 1]\\ \sum_{i = 0} ^{n} i \times \sum_{j = 0} ^{m - 1} [i > \frac{jc + c - b - 1}{a}]\\ \sum_{j = 0} ^{m - 1} \sum_{i = 0} ^{n} i [i > \frac{jc + c - b - 1}{a}]\\ calc(n) = \frac{n \times (n + 1)}{2}\\ \sum_{j = 0} ^{m - 1} calc(n) - calc(\frac{jc + c - b - 1}{a})\\ \frac{m \times n \times (n + 1) - f(a', b', c', m- 1) - h(a', b', c', m - 1)}{2}\\ i=0∑n​i×j=1∑ca×i+b​​1i=0∑n​i×j=1∑m​[ca×i+b​≥j]i=0∑n​i×j=0∑m−1​[ca×i+b​≥j+1]i=0∑n​i×j=0∑m−1​[i>ajc+c−b−1​]j=0∑m−1​i=0∑n​i[i>ajc+c−b−1​]calc(n)=2n×(n+1)​j=0∑m−1​calc(n)−calc(ajc+c−b−1​)2m×n×(n+1)−f(a′,b′,c′,m−1)−h(a′,b′,c′,m−1)​

h ( a , b , c , n ) = ∑ i = 0 n ( a × i + b c ) 2 , ( 0 ≤ a , b , c , n ) h(a, b, c, n) = \sum\limits_{i = 0} ^{n} \left(\frac{a \times i + b}{c} \right) ^ 2, (0 \le a, b, c, n) h(a,b,c,n)=i=0∑n​(ca×i+b​)2,(0≤a,b,c,n)

b ≥ c , b ′ = b   %   c , d = b c b \ge c,b' = b \ \% \ c, d = \frac{b}{c} b≥c,b′=b % c,d=cb​
∑ i = 0 n ( a × i + b ′ c + d ) 2 ∑ i = 0 n ( a × i + b ′ c ) 2 + d 2 + 2 × d × a × i + b ′ c d 2 × ( n + 1 ) + 2 × d × f ( a , b ′ , c , n ) + h ( a , b ′ , c , n ) \sum_{i = 0} ^{n} \left(\frac{a \times i + b'}{c} + d \right) ^2\\ \sum_{i = 0} ^{n} \left(\frac{a \times i + b'}{c} \right) ^ 2 + d ^ 2 + 2 \times d \times \frac{a \times i + b'}{c}\\ d ^ 2 \times (n + 1) + 2 \times d \times f(a, b', c, n) + h(a, b', c, n)\\ i=0∑n​(ca×i+b′​+d)2i=0∑n​(ca×i+b′​)2+d2+2×d×ca×i+b′​d2×(n+1)+2×d×f(a,b′,c,n)+h(a,b′,c,n)
a ≥ c , a ′ = a   %   c , d = a c a \ge c, a' = a\ \%\ c, d = \frac{a}{c} a≥c,a′=a % c,d=ca​
∑ i = 0 n ( d × i + a ′ × i + b c ) 2 ∑ i = 0 n d 2 × i 2 + ( a ′ × i + b c ) 2 + 2 × d × i × a ′ × i + b c d 2 × n × ( n + 1 ) × ( 2 n + 1 ) 6 + h ( a ′ , b , c , n ) + 2 × d × g ( a ′ , b , c , n ) \sum_{i = 0} ^{n} \left(d \times i + \frac{a' \times i + b}{c} \right) ^ 2\\ \sum_{i = 0} ^{n} d ^ 2 \times i ^ 2 + \left(\frac{a' \times i + b}{c} \right) ^ 2 + 2 \times d \times i \times \frac{a' \times i + b}{c}\\ d ^ 2 \times \frac{n \times (n + 1) \times (2n + 1)}{6} + h(a', b, c, n) + 2 \times d \times g(a', b, c, n)\\ i=0∑n​(d×i+ca′×i+b​)2i=0∑n​d2×i2+(ca′×i+b​)2+2×d×i×ca′×i+b​d2×6n×(n+1)×(2n+1)​+h(a′,b,c,n)+2×d×g(a′,b,c,n)
综上， a ≥ c ,   b ≥ c a \ge c,\ b \ge c a≥c, b≥c：

h ( a , b , c , n ) = a c × b c × n × ( n + 1 ) + ( b c ) 2 × ( n + 1 ) + ( a c ) 2 × n × ( n + 1 ) × ( 2 n + 1 ) 6 + 2 × b c × f ( a ′ , b ′ , c , n ) + h ( a ′ , b ′ , c , n ) + 2 × a c × g ( a ′ , b ′ , c , n ) h(a, b, c, n) = \frac{a}{c} \times \frac{b}{c} \times n \times (n + 1) + (\frac{b}{c}) ^ 2 \times (n + 1) + (\frac{a}{c}) ^ 2 \times \frac{n \times (n + 1) \times (2n + 1)}{6}+\\ 2 \times \frac{b}{c} \times f(a', b', c, n) + h(a', b', c, n) + 2 \times \frac{a}{c} \times g(a', b', c, n)\\ h(a,b,c,n)=ca​×cb​×n×(n+1)+(cb​)2×(n+1)+(ca​)2×6n×(n+1)×(2n+1)​+2×cb​×f(a′,b′,c,n)+h(a′,b′,c,n)+2×ca​×g(a′,b′,c,n)

a < c ,   b < c , m = a × n + b c a < c,\ b < c, m = \frac{a \times n + b}{c} a<c, b<c,m=ca×n+b​：

n 2 = 2 × n × ( n + 1 ) 2 − n = 2 × ∑ i = 0 n i − n ∑ i = 0 n ( a × i + b c ) 2 ∑ i = 0 n ( 2 × ∑ j = 0 a × i + b c j − a × i + b c ) h ( a , b , c , n ) = 2 × ∑ i = 0 n ∑ j = 0 a × i + b c j − f ( a , b , c , n ) ∑ i = 0 n ∑ j = 0 a × i + b c j ∑ j = 1 m j ∑ i = 0 n [ a × i + b c ≥ j ] ∑ j = 0 m − 1 ( j + 1 ) ∑ i = 0 n [ a × i + b c ≥ j + 1 ] ∑ j = 0 m − 1 ( j + 1 ) ∑ i = 0 n [ a > j c + c − b − 1 a ] ∑ j = 0 m − 1 ( j + 1 ) ( n − j c + c − b − 1 a ) m × ( m + 1 ) 2 × n − g ( a ′ , b ′ , c ′ , n ) − f ( a ′ , b ′ , c ′ ) h ( a , b , c , n ) = m × ( m + 1 ) × n − f ( a , b , c , n ) − 2 × g ( a ′ , b ′ , c ′ , n ) − 2 × f ( a ′ , b ′ , c ′ , n ) n ^ 2 = 2 \times \frac{n \times (n + 1)}{2} - n = 2 \times \sum_{i = 0} ^{n} i - n\\ \sum_{i = 0} ^{n} (\frac{a \times i + b}{c}) ^ 2\\ \sum_{i = 0} ^{n} \left(2 \times \sum_{j = 0} ^{\frac{a \times i + b}{c}}j - \frac{a \times i + b}{c} \right)\\ h(a, b, c, n) = 2 \times \sum_{i = 0} ^{n} \sum_{j = 0} ^{\frac{a \times i + b}{c}} j - f(a, b, c, n)\\ \sum_{i = 0} ^{n} \sum_{j = 0} ^ \frac{a \times i + b}{c}j\\ \sum_{j = 1} ^{m} j\sum_{i = 0} ^{n} [\frac{a \times i + b}{c} \ge j]\\ \sum_{j = 0} ^{m - 1} (j + 1) \sum_{i = 0} ^{n} [\frac{a \times i + b}{c} \ge j + 1]\\ \sum_{j = 0} ^{m - 1} (j + 1) \sum_{i = 0} ^{n}[a > \frac{jc + c - b - 1}{a}]\\ \sum_{j = 0} ^{m - 1} (j + 1) (n - \frac{jc + c - b - 1}{a})\\ \frac{m \times (m + 1)}{2} \times n - g(a', b', c', n) - f(a', b', c')\\ h(a, b, c, n) = m \times (m + 1) \times n - f(a, b, c, n) - 2 \times g(a', b', c', n) - 2 \times f(a', b', c', n)\\ n2=2×2n×(n+1)​−n=2×i=0∑n​i−ni=0∑n​(ca×i+b​)2i=0∑n​⎝⎛​2×j=0∑ca×i+b​​j−ca×i+b​⎠⎞​h(a,b,c,n)=2×i=0∑n​j=0∑ca×i+b​​j−f(a,b,c,n)i=0∑n​j=0∑ca×i+b​​jj=1∑m​ji=0∑n​[ca×i+b​≥j]j=0∑m−1​(j+1)i=0∑n​[ca×i+b​≥j+1]j=0∑m−1​(j+1)i=0∑n​[a>ajc+c−b−1​]j=0∑m−1​(j+1)(n−ajc+c−b−1​)2m×(m+1)​×n−g(a′,b′,c′,n)−f(a′,b′,c′)h(a,b,c,n)=m×(m+1)×n−f(a,b,c,n)−2×g(a′,b′,c′,n)−2×f(a′,b′,c′,n)

P5170 【模板】类欧几里得算法

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353, inv2 = 499122177, inv6 = 166374059;

struct Res {
  int f, g, h;
};

inline int add(int x, int y) {
  return x + y < mod ? x + y : x + y - mod;
}

inline int sub(int x, int y) {
  return x >= y ? x - y : x - y + mod;
}

Res calc(int a, int b, int c, int n) {
  if (!a) {
    return {1ll * (b / c) * (n + 1) % mod, 1ll * (b / c) * n % mod * (n + 1) % mod * inv2 % mod, 1ll * (b / c) * (b / c) % mod * (n + 1) % mod};
  }
  if (a >= c || b >= c) {
    Res cur= calc(a % c, b % c, c, n);
    int f = add(add(cur.f, 1ll * (b / c) * (n + 1) % mod), 1ll * (a / c) * n % mod * (n + 1) % mod * inv2 % mod);
    int g = add(add(1ll * (b / c) * n % mod * (n + 1) % mod * inv2 % mod, 1ll * (a / c) * n % mod * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod), cur.g);
    int h = add(add(add(1ll * (a / c) * (b / c) % mod * n % mod * (n + 1) % mod, 1ll * (b / c) * (b / c) % mod * (n + 1) % mod), add(1ll * (a / c) * (a / c) % mod * n % mod * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod, 1ll * 2 * (b / c) % mod * cur.f % mod)), add(cur.h, 1ll * 2 * (a / c) * cur.g % mod));
    return {f, g, h};
  }
  int m = (1ll * a * n + b) / c;
  Res cur = calc(c, c - b - 1, a, m - 1);
  int f = sub(1ll * n * m % mod, cur.f);
  int g = 1ll * sub(sub(1ll * m * n % mod * (n + 1) % mod, cur.f), cur.h) * inv2 % mod;
  int h = sub(sub(sub(1ll * m * (m + 1) % mod * n % mod, f), 2ll * cur.g % mod), 2ll * cur.f % mod);
  return {f, g, h};
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  int T, a, b, c, n;
  scanf("%d", &T);
  while (T--) {
    scanf("%d %d %d %d", &n, &a, &b, &c);
    Res ans = calc(a, b, c, n);
    printf("%d %d %d\n", ans.f, ans.h, ans.g);
  }
  return 0;
}