CTime_Pup_314

不能再颓废了

0%

确实学不会的类欧几里得算法

发表于 更新于 分类于 阅读次数： Valine：

所谓类欧几里得就是复杂度与欧几里得算法类似，但其他完全不一样的算法

开始之前，先做一个简单的约定，其中 \(0^0=1\)

\[ \operatorname{S_m}(n)=\sum_{i=0}^ni^m \]

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

设题目中所要求的为

\[ \begin{aligned} &\operatorname{f}(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor\\\\ &\operatorname{g}(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor^2\\\\ &\operatorname{h}(a,b,c,n)=\sum_{i=0}^ni\lfloor\frac{ai+b}{c}\rfloor \end{aligned} \] 我们先从 \(\operatorname{f}\) 入手 首先，有一个很明显的恒等式

\[ \begin{aligned} \lfloor\frac{Ax}{y}\rfloor&=\lfloor\frac{A(y\lfloor\frac{x}{y}\rfloor+x\operatorname{mod}y)}{y}\rfloor\\\\&=\lfloor\frac{A(x\operatorname{mod}y)}{y}\rfloor+A\lfloor\frac{x}{y}\rfloor \end{aligned} \]

所以就有

\[ \begin{aligned} \operatorname{f}(a,b,c,n)&=\operatorname{S_1}(n)\lfloor\frac{a}{c}\rfloor+\operatorname{S_0}(n)\lfloor\frac{b}{c}\rfloor+\sum_{i=0}^n\lfloor\frac{(a\operatorname{mod}c)i+(b\operatorname{mod}c)}{c}\rfloor\\\\&=\operatorname{S_1}(n)\lfloor\frac{a}{c}\rfloor+\operatorname{S_0}(n)\lfloor\frac{b}{c}\rfloor+\operatorname{f}(a\operatorname{mod}c,b\operatorname{mod}c,c) \end{aligned} \]

根据这个我们就可以把 \(a\ge c\) 和 \(b\ge c\) 转化为 \(a<c\) 和 \(b<c\)

那么考虑 \(a<c\land b < c\) 的情形，设 \(m=\lfloor\frac{an+b}{c}\rfloor\)

我们有

\[ \begin{aligned} \operatorname{f}(a,b,c,n)&=\sum_{i=0}^n\sum_{j=1}^m[j\le\lfloor\frac{ai+b}{c}\rfloor]\\\\&=\sum_{j=0}^{m-1}\sum_{i=0}^n[jc+c\le ai+b] \end{aligned} \]

之后我们需要明确

\[ \lfloor\frac{a}{b}\rfloor\le\frac{a}{b}\le\lceil\frac{a}{b}\rceil=\lfloor\frac{a-1}{b}\rfloor+1 \]

当且仅当 \(b|a\) 时等号取到

所以

\[ \begin{aligned} \operatorname{f}(a,b,c,n)&=\sum_{j=0}^{m-1}\sum_{i=0}^n[\lceil\frac{jc+c-b}{a}\rceil\le i]\\\\&=\sum_{j=0}^{m-1}\sum_{i=0}^n[\lfloor\frac{jc+c-b-1}{a}\rfloor< i] \end{aligned} \]

由于 \(\frac{(m-1)c+c-b-1}{a}<n\) 所以式子可以变为

\[ \begin{aligned} \operatorname{f}(a,b,c,n)&=nm-\sum_{j=0}^{m-1}\lfloor\frac{jc+c-b-1}{a}\rfloor\\\\&=nm-\operatorname{f}(c,c-b-1,a,m-1) \end{aligned} \]

这就是一个类似于更相减损的方法了，那么很显然有边界

当 \(a=0\lor n=0\) 时， \(\operatorname{f}(a,b,c,n)=\operatorname{S}_0(n)\lfloor\frac{b}{c}\rfloor\)

之后我们再看 \(\operatorname{g}\)，我们类比 \(\operatorname{f}\) 的过程

首先 \(a\ge c\lor b\ge c\) 时，

\[ \begin{aligned} \operatorname{g}(a,b,c,n)=&\sum_{i=0}^n(\lfloor\frac{(a\operatorname{mod}c)i+(b\operatorname{mod}c)}{c}\rfloor+i\lfloor\frac{a}{c}\rfloor+\lfloor\frac{b}{c}\rfloor)^2\\\\=&\operatorname{S}_2(n)\lfloor\frac{a}{c}\rfloor^2+2\operatorname{S}_1(n)\lfloor\frac{a}{c}\rfloor\lfloor\frac{b}{c}\rfloor+\operatorname{S}_0(n)\lfloor\frac{b}{c}\rfloor^2+\operatorname{g}(a\operatorname{mod}c,b\operatorname{mod}c,c)\\\\&+2\lfloor\frac{a}{c}\rfloor\operatorname{h}(a\operatorname{mod}c,b\operatorname{mod}c,c)+2\lfloor\frac{b}{c}\rfloor\operatorname{f}(a\operatorname{mod}c,b\operatorname{mod}c,c) \end{aligned} \]

接着我们讨论 \(a< c\land b< c\) 不妨设 \(m=\lfloor\frac{an+b}{c}\rfloor\)

\[ \begin{aligned} \operatorname{g}(a,b,c,n)&=\sum_{i=0}^n(\sum_{j=1}^m[j\le\lfloor\frac{ai+b}{c}\rfloor])^2\\\\&=\sum_{i=0}^n\sum_{j=1}^m\sum_{k=1}^m[j\le\lfloor\frac{ai+b}{c}\rfloor][k\le\lfloor\frac{ai+b}{c}\rfloor]\\\\&=\sum_{i=0}^n\sum_{j=0}^{m-1}\sum_{k=0}^{m-1}[\lfloor\frac{jc+c-b-1}{a}\rfloor< i][\lfloor\frac{kc+c-b-1}{a}\rfloor< i]\\\\&=nm^2-\sum_{j=0}^{m-1}\sum_{k=0}^{m-1}\max(\lfloor\frac{jc+c-b-1}{a}\rfloor,\lfloor\frac{kc+c-b-1}{a}\rfloor) \end{aligned} \]

根据对称性不难得到

\[ \begin{aligned} \operatorname{g}(a,b,c,n)&=nm^2-(2\sum_{j=0}^{m-1}(j+1)\lfloor\frac{jc+c-b-1}{a}\rfloor-\sum_{j=0}^{m-1}\lfloor\frac{jc+c-b-1}{a}\rfloor)\\\\&=nm^2-2\operatorname{h}(c,c-b-1,a,m-1)-\operatorname{f}(c,c-b-1,a,m-1) \end{aligned} \]

考虑边界条件 \(a=0\lor n=0\) 则有 \(\operatorname{g}(a,b,c,n)=\operatorname{S}_0(n)\lfloor\frac{b}{c}\rfloor^2\)

最后计算 \(\operatorname{h}\) 同样类比我们可以得到

首先 \(a\ge c\lor b\ge c\) 时

\[ \begin{aligned} \operatorname{h}(a,b,c,n)&=\sum_{i=0}^ni(\lfloor\frac{(a\operatorname{mod}c)i+(b\operatorname{mod}c)}{c}\rfloor+i\lfloor\frac{a}{c}\rfloor+\lfloor\frac{b}{c}\rfloor)\\\\&=\operatorname{S}_2(n)\lfloor\frac{a}{c}\rfloor+\operatorname{S}_1(n)\lfloor\frac{b}{c}\rfloor+\operatorname{h}(a\operatorname{mod}c,b\operatorname{mod}b,c) \end{aligned} \]

其次 \(a<c\land b<c\) 时，同理设 \(m=\lfloor\frac{an+b}{c}\rfloor\) \[ \begin{aligned} \operatorname{h}(a,b,c,n)&=\sum_{i=0}^ni\sum_{j=1}^m[j\le\lfloor\frac{ai+b}{c}\rfloor]\\\\&=\sum_{j=0}^{m-1}\sum_{i=0}^ni[\lfloor\frac{jc+c-b-1}{a}\rfloor<i]\\\\&=\operatorname{S_1}(n)m-\sum_{j=0}^{m-1}\frac{1}{2}(\lfloor\frac{jc+c-b-1}{a}\rfloor+\lfloor\frac{jc+c-b-1}{a}\rfloor^2)\\\\&=\operatorname{S_1}(n)m-\frac{1}{2}\operatorname{f}(c,c-b-1,a,m-1)-\frac{1}{2}\operatorname{g}(c,c-b-1,a,m-1) \end{aligned} \]

最后 \(a=0\lor n=0\) 时 \(\operatorname{h}=\operatorname{S}_1(n)\lfloor\frac{b}{c}\rfloor\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int P = 998244353, I2 = P-(P/2), I6 = 166374059;
struct Euclid { int f, g, h; };
Euclid solve(int a, int b, int c, int64 n)
{
    int64 p = a/c%P, q = b/c%P, p2 = p*p%P, q2 = q*q%P, m = n%P; Euclid E, F;
    int s0 = m+1, s1 = (m+1)*m%P*I2%P, s2 = (m+1)*I6%P*(2*m+1)%P*m%P;
    if(a == 0||n == 0) E.f = s0*q%P, E.g = s0*q2%P, E.h = s1*q%P;
    else if(a >= c||b >= c)
    {
        F = solve(a%c, b%c, c, n);
        E.f = (s1*p+s0*q+F.f)%P;
        E.g = ((s2*p2+2*s1*p%P*q%P+s0*q2)%P+F.g+2*p*F.h%P+2*q*F.f%P)%P;
        E.h = (s2*p+s1*q+F.h)%P;
    }
    else
    {
        m = (a*n+b)/c, n %= P, F = solve(c, c-b-1, a, m-1);
        E.f = (n*m+P-F.f)%P, 
        E.g = (n*m%P*m%P-F.f%P-2*F.h%P+P*2)%P,
        E.h = (s1*m%P-1ll*I2*(F.f+F.g)%P+P)%P;
    }
    return E;
}
int t;
int main()
{
    t = read();
    while(t--)
    {
        int n = read(), a = read(), b = read(), c = read(); Euclid E = solve(a, b, c, n);
        printf("%d %d %d\n", E.f, E.g, E.h);
    }
    return 0;
}