类欧几里得算法推导
初识
给出三种形式：
- f ( a , b , c , n ) = ∑ i = 0 n ⌊ a i + b c ⌋ f(a, b, c, n) = \sum_{i = 0} ^{n} \lfloor\frac{ai + b}{c}\rfloor f(a,b,c,n)=∑i=0n⌊cai+b⌋
- g ( a , b , c , n ) = ∑ i = 0 n i ⌊ a i + b c ⌋ g(a, b, c, n) = \sum_{i = 0} ^{n}i \lfloor \frac{ai + b}{c}\rfloor g(a,b,c,n)=∑i=0ni⌊cai+b⌋
- h ( a , b , c , n ) = ∑ i = 1 n ⌊ a i + b c ⌋ 2 h(a, b, c, n) = \sum_{i = 1} ^{n} \lfloor \frac{ai + b}{c}\rfloor ^ 2 h(a,b,c,n)=∑i=1n⌊cai+b⌋2
接下来我们进入正题，讲解这三个式子的求解
f(a, b, c, n)
f ( a , b , c , n ) = ∑ i = 1 n ⌊ a i + b c ⌋ i f a ≥ c 或 者 b ≥ c f ( a , b , c , n ) = f ( a % c , b % c , c , n ) + n ( n + 1 ) 2 ⌊ a c ⌋ + ( n + 1 ) ⌊ b c ⌋ i f a < c 并 且 b < c 我 们 假 定 m = ⌊ a n + b c ⌋ 有 f ( a , b , c , n ) = ∑ 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 ( i > ⌊ j c + c − b − 1 a ) ⌋ = ∑ j = 0 m − 1 n − ⌊ j c + c − b − 1 a ⌋ = n m − f ( c , c − b − 1 , a , m − 1 ) 也 就 是 a = c , c = a % c 最 后 的 递 归 边 界 就 是 a = 0 f(a, b, c, n) = \sum_{i = 1} ^{n} \lfloor \frac{ai + b}{c} \rfloor\\ if\ a \geq c\ 或者 b \geq c\\ f(a, b, c, n) = f(a \% c, b \% c, c, n) + \frac{n(n + 1)}{2} \lfloor\frac{a}{c}\rfloor + (n + 1) \lfloor \frac{b}{c}\rfloor\\ if\ a < c 并且 b < c\\ 我们假定m = \lfloor\frac{an + b}{c}\rfloor\\ 有f(a, b, c, n) = \sum_{i = 0} ^{n} \sum_{j = 1} ^{m}(\lfloor\frac{ai + b}{c}\rfloor \geq j)\\ = \sum_{i = 0} ^{n} \sum_{j = 0} ^{m - 1} (\lfloor\frac{ai + b}{c}\rfloor \geq j + 1)\\ = \sum_{i = 0} ^{n} \sum_{j = 0} ^{m - 1} (i > \lfloor\frac{jc + c - b - 1}{a})\rfloor\\ = \sum_{j = 0} ^{m - 1} n - \lfloor\frac{jc + c - b - 1}{a}\rfloor\\ = nm - f(c, c - b - 1, a, m - 1)\\ 也就是a = c, c = a \% c\\ 最后的递归边界就是a = 0\\ f(a,b,c,n)=i=1∑n⌊cai+b⌋if a≥c 或者b≥cf(a,b,c,n)=f(a%c,b%c,c,n)+2n(n+1)⌊ca⌋+(n+1)⌊cb⌋if a<c并且b<c我们假定m=⌊can+b⌋有f(a,b,c,n)=i=0∑nj=1∑m(⌊cai+b⌋≥j)=i=0∑nj=0∑m−1(⌊cai+b⌋≥j+1)=i=0∑nj=0∑m−1(i>⌊ajc+c−b−1)⌋=j=0∑m−1n−⌊ajc+c−b−1⌋=nm−f(c,c−b−1,a,m−1)也就是a=c,c=a%c最后的递归边界就是a=0
最后我们就可以通过递归求得其函数值。
g(a, b, c, n)
g ( a , b , c , n ) = ∑ i = 0 n i ⌊ a i + b c ⌋ i f a ≥ c 或 者 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 ⌋ i f a < c 并 且 b < c 同 上 面 式 子 一 样 m = ⌊ a n + b c ⌋ g ( a , b , c , n ) = ∑ i = 0 n i ∑ j = 1 m ( ⌊ a i + b c ⌋ ≥ j ) = ∑ i = 0 n i ∑ j = 0 m − 1 ( i > ⌊ j c + c − b − 1 a ) ⌋ 显 然 有 i 的 下 界 为 ⌊ j c + c − b − 1 a ⌋ + 1 ， 上 界 是 n ， 所 以 构 成 了 一 个 等 差 数 列 最 后 得 到 g ( a , b , c , n ) = ∑ j = 0 m − 1 ⌊ ( ⌊ j c + c − b − 1 a ⌋ + 1 + n ) ( n − ⌊ j c + c − b − 1 a ⌋ ) 2 ⌋ = ⌊ m n ( n + 1 ) − f ( c , c − b − 1 , a , m − 1 ) − h ( c , c − b − 1 , a , m − 1 ) 2 ⌋ 所 以 我 们 先 推 导 h ( a , b , c , n ) g(a, b, c, n) = \sum_{i = 0} ^{n} i\lfloor \frac{ai + b}{c}\rfloor\\ if\ a \geq c 或者 b \geq c\\ g(a, b, c, n) = g(a \%c, b\%c, c, n) + \frac{n(n + 1)(2n + 1)}{6} \lfloor\frac{a}{c}\rfloor + \frac{n(n + 1)}{2} \lfloor\frac{b}{c}\rfloor\\ if\ a < c 并且 b < c\\ 同上面式子一样m = \lfloor\frac{an + b}{c}\rfloor\\ g(a, b, c, n) = \sum_{i = 0} ^{n}i \sum_{j = 1} ^{m} (\lfloor\frac{ai + b}{c}\rfloor \geq j)\\ = \sum_{i = 0} ^{n} i\sum_{j = 0} ^{m - 1} (i > \lfloor\frac{jc + c - b - 1}{a})\rfloor\\ 显然有i的下界为\lfloor\frac{jc + c - b - 1}{a}\rfloor + 1，上界是n，所以构成了一个等差数列\\ 最后得到g(a, b, c, n) = \sum_{j = 0} ^{m - 1} \lfloor\frac{(\lfloor\frac{jc + c - b - 1}{a}\rfloor + 1 + n)(n - \lfloor\frac{jc + c - b - 1}{a}\rfloor)}{2}\rfloor\\ = \lfloor\frac{mn(n + 1) - f(c, c - b - 1, a, m - 1) - h(c, c - b - 1, a, m - 1)}{2}\rfloor\\ 所以我们先推导h(a, b, c, n)\\ g(a,b,c,n)=i=0∑ni⌊cai+b⌋if a≥c或者b≥cg(a,b,c,n)=g(a%c,b%c,c,n)+6n(n+1)(2n+1)⌊ca⌋+2n(n+1)⌊cb⌋if a<c并且b<c同上面式子一样m=⌊can+b⌋g(a,b,c,n)=i=0∑nij=1∑m(⌊cai+b⌋≥j)=i=0∑nij=0∑m−1(i>⌊ajc+c−b−1)⌋显然有i的下界为⌊ajc+c−b−1⌋+1，上界是n，所以构成了一个等差数列最后得到g(a,b,c,n)=j=0∑m−1⌊2(⌊ajc+c−b−1⌋+1+n)(n−⌊ajc+c−b−1⌋)⌋=⌊2mn(n+1)−f(c,c−b−1,a,m−1)−h(c,c−b−1,a,m−1)⌋所以我们先推导h(a,b,c,n)
h(a, b, c, n)
h ( a , b , c , n ) = ∑ i = 0 n ⌊ a i + b c ⌋ 2 i f a ≥ c 或 者 b ≥ c h ( a , b , c , n ) = ∑ i = 0 n ( i ( a % c ) + b % c c + ⌊ a c ⌋ i + ⌊ b c ⌋ ) 2 = ∑ i = 0 n ( i ( a % c ) + b % c c ) 2 + ∑ i = 0 n ⌊ a c ⌋ 2 i 2 + ∑ i = 0 n ⌊ b c ⌋ 2 + 2 ⌊ a c ⌋ ∑ i = 0 n i i ( a % c ) + b % c c + 2 ⌊ b c ⌋ ∑ i = 0 n i ( a % c ) + b % c c + 2 ⌊ a c ⌋ ⌊ b c ⌋ ∑ i = 0 n i = h ( a % c , b % c , c , n ) + 2 ⌊ b c ⌋ f ( a % c , b % c , c , n ) + 2 ⌊ a c ⌋ g ( a % c , b % c , c , n ) + n ( n + 1 ) ( 2 n + 1 ) 6 ⌊ a c ⌋ 2 + n ( n + 1 ) ⌊ a c ⌋ ⌊ b c ⌋ + ( n + 1 ) ⌊ b c ⌋ 2 i f a < c 并 且 b < c n 2 = 2 n ( n + 1 ) 2 − n = ( 2 ∑ i = 0 n i ) − n h ( a , b , c , n ) = ∑ i = 0 n ( 2 ∑ j = 0 ⌊ a i + b c ⌋ j ) − ⌊ a i + b c ⌋ m = ⌊ a n + b c ⌋ h ( a , b , c , n ) = 2 ∑ j = 0 m − 1 ( j + 1 ) ∑ i = 0 n ( ⌊ a i + b c ⌋ ≥ j + 1 ) − f ( a , b , c , n ) = 2 ∑ j = 0 m ( j + 1 ) ∑ i = 0 n i > ⌊ c j + c − b − 1 a ⌋ = ∑ j = 0 n ( j + 1 ) ( n − ⌊ c j + c − b − 1 a ) ⌋ ) − f ( a , b , c , n ) = 2 ( ∑ j = 1 m j n − ∑ j = 0 m − 1 ( j + 1 ) ⌊ c j + c − b − 1 a ) ⌋ ) − f ( a , b , c , n ) 最 后 得 到 h ( a , b , c , n ) = n m ( m + 1 ) − 2 f ( c , c − b − 1 , a , m − 1 ) − 2 g ( c , c − b − 1 , a , m − 1 ) − f ( a , b , c , n ) h(a, b, c, n) = \sum_{i = 0} ^{n} \lfloor\frac{ai + b}{c}\rfloor ^ 2\\ if\ a \geq c\ 或者 b \geq c\\ h(a, b, c, n) = \sum_{i = 0} ^{n}\left( \frac{i(a \% c) + b \% c}{c} + \lfloor\frac{a}{c}\rfloor i + \lfloor \frac{b}{c}\rfloor \right)^ 2\\ = \sum_{i = 0} ^{n} \left( \frac{i(a \% c) + b \% c}{c}\right)^ 2 + \sum_{i = 0} ^{n} \lfloor\frac{a}{c}\rfloor ^ 2 i ^ 2 + \sum_{i = 0} ^{n} \lfloor \frac{b}{c}\rfloor ^ 2 + 2\lfloor\frac{a}{c}\rfloor \sum_{i = 0} ^{n} i \frac{i(a \% c) + b \% c}{c} + 2 \lfloor\frac{b}{c}\rfloor \sum_{i = 0} ^{n}\frac{i(a \% c) + b \% c}{c} + 2\lfloor\frac{a}{c}\rfloor \lfloor \frac{b}{c}\rfloor \sum_{i = 0} ^{n}i \\ = h(a\%c, b \%c, c, n) + 2 \lfloor \frac{b}{c}\rfloor f(a \%c,b \%c,c,n) +2 \lfloor\frac{a}{c}\rfloor g(a \%c, b\%c, c, n) + \frac{n(n + 1)(2n + 1)}{6}\lfloor\frac{a}{c} \rfloor ^ 2 +n(n + 1) \lfloor\frac{a}{c}\rfloor \lfloor \frac{b}{c}\rfloor + (n + 1) \lfloor\frac{b}{c}\rfloor ^ 2\\ if\ a < c 并且 b < c\\ n ^ 2 = 2 \frac{n(n + 1)}{2} - n = (2\sum_{i = 0} ^{n} i )- n\\ h(a, b, c, n) = \sum_{i = 0} ^{n} (2\sum_{j = 0} ^{\lfloor \frac{ai + b}{c}\rfloor} j) - \lfloor \frac{ai + b}{c}\rfloor\\ m = \lfloor \frac{an + b}{c} \rfloor\\ h(a, b, c, n) = 2 \sum_{j = 0} ^{m - 1}(j + 1) \sum_{i = 0} ^{n} (\lfloor \frac{ai + b}{c}\rfloor \geq j + 1) - f(a, b, c, n)\\ = 2\sum_{j = 0} ^{m} (j + 1) \sum_{i = 0} ^{n} i > \lfloor \frac{cj + c-b-1}{a}\rfloor= \sum_{j = 0} ^{n}(j + 1)(n - \lfloor \frac{cj + c-b-1}{a})\rfloor) - f(a, b, c, n) \\ = 2\left( \sum_{j = 1} ^{m} jn - \sum_{j = 0} ^{m - 1}(j + 1)\lfloor \frac{cj + c-b-1}{a})\rfloor \right) - f(a, b, c, n) \\ 最后得到h(a, b, c, n) = nm(m + 1) - 2f(c, c - b - 1, a, m - 1) - 2g(c, c - b - 1, a, m - 1)- f(a, b, c, n)\\ h(a,b,c,n)=i=0∑n⌊cai+b⌋2if a≥c 或者b≥ch(a,b,c,n)=i=0∑n(ci(a%c)+b%c+⌊ca⌋i+⌊cb⌋)2=i=0∑n(ci(a%c)+b%c)2+i=0∑n⌊ca⌋2i2+i=0∑n⌊cb⌋2+2⌊ca⌋i=0∑nici(a%c)+b%c+2⌊cb⌋i=0∑nci(a%c)+b%c+2⌊ca⌋⌊cb⌋i=0∑ni=h(a%c,b%c,c,n)+2⌊cb⌋f(a%c,b%c,c,n)+2⌊ca⌋g(a%c,b%c,c,n)+6n(n+1)(2n+1)⌊ca⌋2+n(n+1)⌊ca⌋⌊cb⌋+(n+1)⌊cb⌋2if a<c并且b<cn2=22n(n+1)−n=(2i=0∑ni)−nh(a,b,c,n)=i=0∑n(2j=0∑⌊cai+b⌋j)−⌊cai+b⌋m=⌊can+b⌋h(a,b,c,n)=2j=0∑m−1(j+1)i=0∑n(⌊cai+b⌋≥j+1)−f(a,b,c,n)=2j=0∑m(j+1)i=0∑ni>⌊acj+c−b−1⌋=j=0∑n(j+1)(n−⌊acj+c−b−1)⌋)−f(a,b,c,n)=2(j=1∑mjn−j=0∑m−1(j+1)⌊acj+c−b−1)⌋)−f(a,b,c,n)最后得到h(a,b,c,n)=nm(m+1)−2f(c,c−b−1,a,m−1)−2g(c,c−b−1,a,m−1)−f(a,b,c,n)
总结
f ( a , b , c , n ) f(a, b, c, n) f(a,b,c,n)是可以单独求的，但是 g ( a , b , c , n ) , h ( a , b , c , n ) g(a, b, c, n), h(a, b, c, n) g(a,b,c,n),h(a,b,c,n)是得互相得到并且要通过 f ( a , b , c , n ) f(a, b, c, n) f(a,b,c,n)得到，所以我们可以通过一个结构体一次求得三个函数的值，然后一起返回。
P5170 【模板】类欧几里得算法
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define endl '\n'
#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define ls rt << 1
#define rs rt << 1 | 1
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int inf = 0x3f3f3f3f;
inline ll read() {
ll f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return f * x;
}
const int mod = 998244353, inv2 = 499122177, inv6 = 166374059;
struct Node {
ll f, g, h;
};
ll quick_pow(ll a, ll n) {
ll ans = 1;
while(n) {
if(n & 1) ans = ans * a % mod;
a = a * a % mod;
n >>= 1;
}
return ans;
}
Node solve(ll a, ll b, ll c, ll n) {
Node ans, temp;
if(!a) {
ans.f = (n + 1) * (b / c) % mod;
ans.g = (n + 1) * n % mod * inv2 % mod * (b / c) % mod;
ans.h = (n + 1) * (b / c) % mod * (b / c) % mod;
return ans;
}
if(a >= c || b >= c) {
temp = solve(a % c, b % c, c, n);
ans.f = (temp.f + n * (n + 1) % mod * inv2 % mod * (a / c) % mod + (n + 1) * (b / c) % mod) % mod;
ans.g = (temp.g + n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod * (a / c) % mod + n * (n + 1) % mod * inv2 % mod * (b / c) % mod) % mod;
ans.h = (temp.h + 2 * (b / c) % mod * temp.f % mod + 2 * (a / c) % mod * temp.g % mod + n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod * (a / c) % mod * (a / c) % mod + n * (n + 1) % mod * (a / c) % mod * (b / c) % mod + (n + 1) * (b / c) % mod * (b / c) % mod) % mod;
return ans;
}
ll m = (a * n + b) / c;
temp = solve(c, c - b - 1, a, m - 1);
ans.f = (n * m % mod - temp.f + mod) % mod;
ans.g = ((m * n % mod * (n + 1) % mod - temp.f - temp.h) % mod * inv2 % mod + mod) % mod;
ans.h = ((n * m % mod * (m + 1) % mod - 2 * temp.f % mod - 2 * temp.g % mod - ans.f) % mod + mod) % mod;
return ans;
}
int main() {
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T = read();
while(T--) {
ll n = read(), a = read(), b = read(), c = read();
Node ans = solve(a, b, c, n);
printf("%lld %lld %lld\n", ans.f, ans.h, ans.g);
}
return 0;
}
