类欧几里得算法

发表于 更新于 分类于

题目链接

花一上午学了下这个东西,记录一下方便以后复习,以下主要靠抄OI-Wiki ## 题目
给定\(n,a,b,c\).计算:
\[ f(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor \frac{ai+b}{c} \right\rfloor \] \[ g(a,b,c,n)=\sum\limits_{i=0}^ni\left\lfloor \frac{ai+b}{c} \right\rfloor \] \[ h(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor \frac{ai+b}{c} \right\rfloor^2 \]

题解

f函数

\[ f(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor \frac{ai+b}{c} \right\rfloor \] 可以把原来的式子变化一下.
$ f(a,b,c,n)=_{i=0}^n  $

\(=\sum\limits_{i=0}^n\left\lfloor \frac{\left(\left\lfloor\frac{a}{c}\right\rfloor c+a\bmod c\right)i+\left(\left\lfloor\frac{b}{c}\right\rfloor c+b\bmod c\right)}{c}\right\rfloor\ \)

\(=\frac{n(n+1)}{2}\left\lfloor\frac{a}{c}\right\rfloor+(n+1)\left\lfloor\frac{b}{c}\right\rfloor+ \sum\limits_{i=0}^n\left\lfloor\frac{\left(a\bmod c\right)i+\left(b\bmod c\right)}{c} \right\rfloor\ \)

\(=\frac{n(n+1)}{2}\left\lfloor\frac{a}{c}\right\rfloor +(n+1)\left\lfloor\frac{b}{c}\right\rfloor+f(a\bmod c,b\bmod c,c,n)\)

现在只用考虑\(a<c,b<c\)的情况.
把式子变化一下, \[f(a,b,c,n)=\sum\limits_{i=0}^n\sum\limits_{j=0}^{\left\lfloor \frac{ai+b}{c} \right\rfloor-1}1\]
因为想办法把\(i\)处理掉,常见的方法是交换求和符号.
\[\sum\limits_{j=0}^{\left\lfloor \frac{an+b}{c} \right\rfloor-1} \sum\limits_{i=0}^n\left[j<\left\lfloor \frac{ai+b}{c} \right\rfloor\right]\]

因为\(j<\left\lfloor \frac{ai+b}{c} \right\rfloor\Leftrightarrow j+1\leq \left\lfloor \frac{ai+b}{c} \right\rfloor\Leftrightarrow j+1\leq \frac{ai+b}{c}\Leftrightarrow cj+c\leq ai+b\Leftrightarrow \left\lfloor\frac{cj+c-b-1}{a}\right\rfloor<i\)
所以也等价于
\(\sum\limits_{j=0}^{\left\lfloor \frac{an+b}{c} \right\rfloor-1} \sum\limits_{i=0}^n\left[\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor<i\right]\)
\(=\sum\limits_{j=0}^{\left\lfloor \frac{an+b}{c} \right\rfloor-1}n-\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor\)
\(=\left\lfloor \frac{an+b}{c} \right\rfloor\times n-f(c,c-b-1,a,\left\lfloor \frac{an+b}{c} \right\rfloor-1)\)
发现\(a,c\)也恰好是交换的,是可以像欧几里得算法那样递归处理.
### g函数 \[ g(a,b,c,n)=\sum\limits_{i=0}^ni\left\lfloor \frac{ai+b}{c} \right\rfloor \]

好像和上面挺相似的.
\[ g(a,b,c,n) =g(a\bmod c,b\bmod c,c,n)+\left\lfloor\frac{a}{c}\right\rfloor\frac{n(n+1)(2n+1)}{6}+\left\lfloor\frac{b}{c}\right\rfloor\frac{n(n+1)}{2} \]

然后考虑\(b<c,a<c\)的情况
\(g(a,b,c,n)=\sum\limits_{i=0}^ni\left\lfloor \frac{ai+b}{c} \right\rfloor\)
\(=\sum\limits_{j=0}^{m-1} \sum\limits_{i=0}^n\left[j<\left\lfloor\frac{ai+b}{c}\right\rfloor\right]\cdot i\)
\(=\sum\limits_{j=0}^{m-1}\sum\limits_{i=0}^n\left[\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor<i\right]\cdot i\)
\(=\sum\limits_{j=0}^{m-1}\frac{1}{2}\cdot (t+n+1)(n-t)\)
\(=\frac{1}{2}\sum\limits_{j=0}^{m-1}n(n+1)-t^2-t\)
\(=\frac{1}{2}mn(n+1)-\frac{1}{2}\sum\limits_{j=0}^{m-1}t-\frac{1}{2}\sum\limits_{j=0}^{m-1}t^2\)
\(=\frac{1}{2}mn(n+1)-\frac{1}{2}f(c,c-b-1,a,m-1)-\frac{1}{2}h(c,c-b-1,a,m-1)\)

其中\(m=\left\lfloor\frac{an+b}{c}\right\rfloor\),\(t=\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor\).

h函数

\[ h(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor \frac{ai+b}{c} \right\rfloor^2 \]
这个要复杂一些.
还是先取模.
\(h(a,b,c,n)=h(a\bmod c,b\bmod c,c,n) +2\left\lfloor\frac{b}{c}\right\rfloor f(a\bmod c,b\bmod c,c,n) +2\left\lfloor\frac{a}{c}\right\rfloor g(a\bmod c,b\bmod c,c,n)+\left\lfloor\frac{a}{c}\right\rfloor^2\frac{n(n+1)(2n+1)}{6}+\left\lfloor\frac{b}{c}\right\rfloor^2(n+1) +\left\lfloor\frac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor n(n+1)\)

把平方拆开

\[ n^2=2\frac{n(n+1)}{2}-n=\left(2\sum\limits_{i=0}^ni\right)-n\]

这样添加变量的时候就不会出现两个求和符号相乘,即\(\sum\times \sum\)

$ h(a,b,c,n)=_{i=0}^n ^2$

$ =_{i=0}^n $

$=(2{i=0}^n{j=1}^{ }j) -f(a,b,c,n) $

化简前一部分
\(\ \sum\limits_{i=0}^n\sum\limits_{j=1}^{\left\lfloor \frac{ai+b}{c} \right\rfloor}j\)
$={i=0}^n{j=0}^{ }(j+1) $
\(=\sum\limits_{j=0}^{m-1}(j+1) \sum\limits_{i=0}^n\left[j<\left\lfloor \frac{ai+b}{c} \right\rfloor\right]\)
\(=\sum\limits_{j=0}^{m-1}(j+1)\sum\limits_{i=0}^n[i>t]\) \(=\sum\limits_{j=0}^{m-1}(j+1)(n-t)\) \(=\frac{1}{2}nm(m+1)-\sum\limits_{j=0}^{m-1}(j+1)\left\lfloor \frac{jc+c-b-1}{a} \right\rfloor\) \(=\frac{1}{2}nm(m+1)-g(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)\)

最后, \(h(a,b,c,n)=nm(m+1)-2\cdot g(c,c-b-1,a,m-1)-2\cdot f(c,c-b-1,a,m-1)-f(a,b,c,n)\)

代码

因为这三个函数不全是独立的,且计算的过程大致相同,所以应该一起递归计算.

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
46
47
48
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int P = 998244353, i2 = 499122177, i6 = 166374059;

struct node {
    int f, g, h;
    node() {f = g = h = 0;}
};
node calc(int n, int a, int b, int c) {
    int ac = a / c, bc = b / c, m = (a * n + b) / c, n1 = n + 1, n2 = n * 2 + 1;
    node d;
    if (a == 0) {
        d.f = bc * n1 % P;
        d.g = bc * n % P * n1 % P * i2 % P;
        d.h = bc * bc % P * n1 % P;
        return d;
    }
    if (a >= c || b >= c) {
        d.f = (n * n1 % P * i2 % P * ac % P + bc * n1 % P) % P;
        d.g = (ac * n % P * n1 % P * n2 % P * i6 % P + bc * n % P * n1 % P * i2 % P) % P;
        d.h = (ac * ac % P * n % P * n1 % P * n2 % P * i6 % P + bc * bc % P * n1 % P + ac * bc % P * n % P * n1 % P) % P;
        node e = calc(n, a % c, b % c, c);
        d.g += e.g, d.f += e.f;
        d.h += e.h + 2 * bc % P * e.f % P + 2 * ac % P * e.g % P;
        d.g %= P, d.f %= P, d.h %=P;
        return d;
    }
    node e = calc(m - 1, c, c - b - 1, a);
    d.f = n * m % P - e.f, d.f = (d.f % P + P) % P;
    d.g = m * n % P * n1 % P - e.h - e.f, d.g = (d.g * i2 % P + P) % P;
    d.h = n * m % P * (m + 1) % P - 2 * e.g - 2 * e.f - d.f;
    d.h = (d.h % P + P) % P;
    return d;
}

main() {
    int t;
    scanf("%lld", &t);
    while (t--) {
        int n, a, b, c;
        scanf("%lld %lld %lld %lld", &n, &a, &b, &c);
        node res = calc(n, a, b, c);
        printf("%lld %lld %lld\n", res.f, res.h, res.g);
    }
    return 0;
}