题解 P5170 【【模板】类欧几里得算法】
Cyhlnj
·
·
题解
提供一个推导第二个式子的比较 naive 的暴力思路
定义
定义几个东西，方便表示
设
f(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor
g(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor^2
h(a,b,c,n)=\sum_{i=0}^{n}i\lfloor\frac{ai+b}{c}\rfloor
t_1=\lfloor\frac{a}{c}\rfloor,t_2=\lfloor\frac{b}{c}\rfloor
S_1(n)=\sum_{i=1}^{n}i,S_2(n)=\sum_{i=1}^{n}i^2
m=\lfloor\frac{an+b}{c}\rfloor-1
[i=0]$ 表示条件，即 $i=0$ 就是 $1$，否则为 $0
式子1
首先 a\ge c~~or~~b\ge c 的时候
\lfloor\frac{ai+b}{c}\rfloor=t_1i+t_2+\lfloor\frac{(a~mod~c)i+(b~mod~c)}{c}\rfloor
那么
f(a,b,c,n)=t_1S_1(n)+(n+1)t_2+f(a~mod~c,b~mod~c,c,n)
然后当 a < c~and~b < c 的时候
f(a,b,c,n)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor=\sum_{i=0}^{n}\sum_{j=1}^{m+1}[j\le \lfloor\frac{ai+b}{c}\rfloor]=\sum_{j=0}^{m}\sum_{i=0}^{n}[j+1\le\lfloor\frac{ai+b}{c}\rfloor]
=\sum_{j=0}^{m}\sum_{i=0}^{n}[cj+c\le ai+b]=\sum_{j=0}^{m}\sum_{i=0}^{n}[ai> cj+c-b-1]
=\sum_{j=0}^{m}\sum_{i=0}^{n}[i> \lfloor\frac{cj+c-b-1}{a}\rfloor]=\sum_{j=0}^{m}(n-\lfloor\frac{cj+c-b-1}{a}\rfloor)
=n(m+1)-\sum_{j=0}^{m}\lfloor\frac{cj+c-b-1}{a}\rfloor=n(m+1)-f(c,c-b-1,a,m)
式子2
同样的考虑 a\ge c~~or~~b\ge c 的时候
\lfloor\frac{ai+b}{c}\rfloor^2=(t_1i+t_2+\lfloor\frac{(a~mod~c)i+(b~mod~c)}{c}\rfloor)^2
暴力拆开得到
g(a,b,c,n)=t_1^2S_2(n)+(n+1)t_2^2+2t_1t_2S_1(n)+2t_1h(a~mod~c,b~mod~c,c)
+2t_2f(a~mod~c,b~mod~c,c)+g(a~mod~c,b~mod~c,c)
然后当 a < c~and~b < c 的时候，仍然可以像式子1那样
g(a,b,c,n)=\sum_{i=0}^{n}(\sum_{j=1}^{m+1}[j\le \lfloor\frac{ai+b}{c}\rfloor])^2=\sum_{i=0}^{n}\sum_{j=1}^{m+1}[j\le \lfloor\frac{ai+b}{c}\rfloor])\sum_{k=1}^{m+1}[k\le \lfloor\frac{ai+b}{c}\rfloor])
运用式子1一样的技巧，把 k,j 移到前面
g(a,b,c,n)=\sum_{j=0}^{m}\sum_{k=0}^{m}\sum_{i=0}^{n}[i> \lfloor\frac{cj+c-b-1}{a}\rfloor~and~i> \lfloor\frac{ck+c-b-1}{a}\rfloor]
=\sum_{j=0}^{m}\sum_{k=0}^{m}\sum_{i=0}^{n}[i> max(\lfloor\frac{cj+c-b-1}{a}\rfloor,\lfloor\frac{ck+c-b-1}{a})]
=\sum_{j=0}^{m}\sum_{k=0}^{m}(n-max(\lfloor\frac{cj+c-b-1}{a}\rfloor,\lfloor\frac{ck+c-b-1}{a}))
=n(m+1)^2-\sum_{j=0}^{m}\sum_{k=0}^{m}max(\lfloor\frac{cj+c-b-1}{a}\rfloor,\lfloor\frac{ck+c-b-1}{a})
先算强制 $k$ 的小于等于 $j$ 的，加上 $k$ 的大于等于 $j$ 的，减去相同 $j,k$ 的
前面两个情况显然一样，那么就是
$$n(m+1)^2-2\sum_{j=0}^{m}(j+1)\lfloor\frac{cj+c-b-1}{a}\rfloor+\sum_{j=0}^{m}\lfloor\frac{cj+c-b-1}{a}\rfloor$$
把 $j+1$ 拆开就变成了
$$g(a,b,c,n)=n(m+1)^2-2h(c,c-b-1,a,m)-f(c,c-b-1,a,m)$$
而仔细想一下这个东西和其它的题解实际上是一样的
~~一开始我还以为推错了~~
## 式子3
还是考虑 $a\ge c~~or~~b\ge c$ 的时候
$i\lfloor\frac{ai+b}{c}\rfloor=t_1i^2+t_2i+i\lfloor\frac{(a~mod~c)i+(b~mod~c)}{c}\rfloor
那么
h(a,b,c,n)=t_1S_2(n)+t_2S_1(n)+h(a~mod~c,b~mod~c,c,n)
然后当 a < c~and~b < c 的时候，还是可以像式子1那样
h(a,b,c,n)=\sum_{j=0}^{m}\sum_{i=0}^{n}i[i> \lfloor\frac{cj+c-b-1}{a}\rfloor]=\sum_{j=0}^{m}\sum_{i=\lfloor\frac{cj+c-b-1}{a}\rfloor+1}^{n}i
等差数列求个和，即
h(a,b,c,n)=\frac{1}{2}((m+1)n(n+1)-f(c,c-b-1,a,m)-g(c,c-b-1,a,m))
```cpp
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod(998244353);
const int inv2((mod + 1) >> 1);
const int inv6(166374059);
inline void Inc(int &x, int y) {
x = x + y >= mod ? x + y - mod : x + y;
}
inline void Dec(int &x, int y) {
x = x - y < 0 ? x - y + mod : x - y;
}
inline int Add(int x, int y) {
return x + y >= mod ? x + y - mod : x + y;
}
inline int Sub(int x, int y) {
return x - y < 0 ? x - y + mod : x - y;
}
inline int Pow(ll x, int y) {
ll ret = 1;
for (; y; y >>= 1, x = x * x % mod)
if (y & 1) ret = ret * x % mod;
return ret;
}
inline int Gcd(int x, int y) {
return !y ? x : Gcd(y, x % y);
}
struct Info {
int f, g, h;
} ans;
int test;
inline int S1(ll x) {
return x * (x + 1) / 2 % mod;
}
inline int S2(ll x) {
return x * (x + 1) % mod * (x + x + 1) % mod * inv6 % mod;
}
Info Solve(int a, int b, int c, int n) {
Info ret, frm;
int m, t1, t2, s1, s2;
ret.f = ret.g = ret.h = 0;
if (!n) {
ret.f = b / c, ret.g = (ll)(b / c) * (b / c) % mod;
return ret;
}
if (!a) {
t1 = b / c;
ret.f = (ll)(n + 1) * t1 % mod;
ret.g = (ll)(n + 1) * t1 % mod * t1 % mod;
ret.h = (ll)S1(n) * t1 % mod;
return ret;
}
if (a >= c || b >= c) {
t1 = a / c, t2 = b / c;
frm = Solve(a % c, b % c, c, n);
s1 = S1(n), s2 = S2(n);
ret.f = Add(Add((ll)s1 * t1 % mod, (ll)(n + 1) * t2 % mod), frm.f);
ret.g = Add((ll)t1 * t1 % mod * s2 % mod, (ll)(n + 1) * t2 % mod * t2 % mod);
Inc(ret.g, Add((ll)t1 * t2 % mod * 2 * s1 % mod, (ll)t1 * 2 * frm.h % mod));
Inc(ret.g, Add(frm.g, (ll)t2 * 2 * frm.f % mod));
ret.h = Add(Add((ll)s2 * t1 % mod, (ll)s1 * t2 % mod), frm.h);
return ret;
}
m = ((ll)n * a + b) / c - 1;
frm = Solve(c, c - b - 1, a, m);
ret.f = Sub((ll)n * (m + 1) % mod, frm.f);
ret.g = Sub((ll)n * (m + 1) % mod * (m + 1) % mod, Add(frm.h * 2 % mod, frm.f));
ret.h = Sub((ll)n * (n + 1) % mod * (m + 1) % mod, Add(frm.f, frm.g));
ret.h = (ll)ret.h * inv2 % mod;
return ret;
}
int main() {
int a, b, c, n;
scanf("%d", &test);
while (test) {
scanf("%d%d%d%d", &n, &a, &b, &c);
ans = Solve(a, b, c, n), --test;
printf("%d %d %d\n", ans.f, ans.g, ans.h);
}
return 0;
}
```