P5170类欧几里得算法推式子过程

· · 个人记录

原题一共有三问：

答案对 998244353 取模。

第一问

分类讨论。

(a \ge c )\vee(b \ge c)

众所周知 \lfloor \frac{a}{c} \rfloor \iff \lfloor \frac{\lfloor \frac{a}{c} \rfloor c+(a\bmod c)}{c} \rfloor

所以我们有

\begin{aligned} &F(a, b, c, n) \\ =&\sum_{i = 0}^{n}\left\lfloor\frac{a i+b}{c}\right\rfloor \\ =&\sum_{i = 0}^{n}\left(\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\right) \\ =&\sum_{i = 0}^{n}\left(\left\lfloor\frac{(a \bmod c) i+(b \bmod c)}{c}\right\rfloor+i\left\lfloor\frac{a}{c}\right\rfloor+\left\lfloor\frac{b}{c}\right\rfloor\right) \\ =&\sum_{i = 0}^{n}\left\lfloor\frac{(a \bmod c) i+(b \bmod c)}{c}\right\rfloor+\sum_{i = 0}^{n} i\left\lfloor\frac{a}{c}\right\rfloor+\sum_{i = 0}^{n}\left\lfloor\frac{b}{c}\right\rfloor \\ =&F(a \bmod c, b \bmod c, c, n)+\frac{n(n+1)}{2}\left\lfloor\frac{a}{c}\right\rfloor+(n+1)\left\lfloor\frac{b}{c}\right\rfloor \end{aligned}

(a<c) \wedge (b<c)

我们需要知道两个前置芝士：

知道了这个，我们来化简原式。

F(a,b,c,n)=\sum_{i=0}^{n}\left\lfloor \frac{ai+b}{c} \right\rfloor=\sum_{i=0}^n\sum_{j=0}^{\left\lfloor\frac{ai+b}{c}\right\rfloor-1} 1

对于两层 \sum，我们可以调换顺序，只是需要稍微修改一下，变为

\sum_{j=0}^{\left \lfloor \frac{an+b}{c} \right\rfloor -1} \sum_{i=0}^{n}\left[j<\left\lfloor \frac{ai+b}{c}\right \rfloor\right]

接下来我们化简艾弗森括号中的内容。

\begin{aligned} &j<\left \lfloor \frac{ai+b}{c} \right\rfloor\\ \Rightarrow &j+1 \le \left \lfloor \frac{ai+b}{c} \right \rfloor\\ \Rightarrow &j+1 \le \frac{ai+b}{c}\\ \Rightarrow &j+c+c-b \le ai\\ \Rightarrow &jc+c-b-1 < ai\\ \Rightarrow &i>\left \lfloor \frac{jc+c-b-1}{a}\right \rfloor \end{aligned}

我们“承上启下”，把它套回去

\sum^{\lfloor \frac{an+b}{c} \rfloor-1}_{j=0}(n-\left \lfloor \frac{jc+c-b-1}{a} \right \rfloor)

令 m=\left\lfloor \frac{an+b}{c} \right\rfloor

那么我们有

\begin{aligned} &F(a,b,c,n)\\ =&\sum_{i=0}^{m-1}\left(n-\left\lfloor \frac{ci+(c-b-1)}{a} \right\rfloor\right) \\ =&\sum_{i=0}^{m-1}n-\sum_{i=0}^{m-1}\left\lfloor \frac{ci+(c-b-1)}{a} \right\rfloor\\ =&nm-F(c,c-b-1,a,m-1) \end{aligned}

边界情况

当 $a=0$ 时， $$ \begin{aligned} &F(0,b,c,n)\\ =&\sum_{i=0}^{n} \lfloor \frac{b}{c} \rfloor\\ =&(n+1)\lfloor \frac{b}{c} \rfloor \end{aligned} $$ 还有一种边界情况，当 $n=0$ 时，$F(a,b,c,0)$ 显然为 $\lfloor \frac{b}{c} \rfloor$。 ## 总结 把上面的内容结合起来，就能得出最终式子了。 $$ F(a, b, c, n)= \left\{\begin{array}{c} (n+1)\left\lfloor\frac{b}{c}\right\rfloor & a=0 \\ \left\lfloor\frac{b}{c}\right\rfloor&n=0 \\ F(a \bmod c, b \bmod c, c, n)+\frac{n(n+1)}{2}\left\lfloor\frac{a}{c}\right\rfloor+(n+1)\left\lfloor\frac{b}{c}\right\rfloor&(a \geq c) \vee (b \geq c)\\ n m-F(c, c-b-1, a, m-1) &(a<c) \wedge (b<c) \end{array}\right. $$ # 第二问 还是分类讨论。 ## $(a \ge c )\vee(b \ge c) \begin{aligned} &G(a,b,c,n)\\ =&\sum^{n}_{i=0}\left \lfloor \frac{ai+b}{c}\right \rfloor ^2\\ =&\sum^n_{i=0}\left \lfloor \frac{\left (\left \lfloor \frac{a}{c}\right \rfloor c +(a\bmod c) \right )i+\left \lfloor \frac{b}{c}\right \rfloor c+(b \bmod c)}{c} \right \rfloor ^2\\ =&\sum^n_{i=0}\left \lfloor \left \lfloor \frac{a}{c} \right \rfloor i+\left \lfloor \frac{b}{c} \right \rfloor +\frac{(a \bmod c)i+(b \bmod c)}{c} \right \rfloor ^2 \end{aligned}

依旧需要一些前置芝士：

(a+b+c)^2=a^2+b^2+c^2+2ab+2bc+2ca

令 t=\left \lfloor \frac{a\bmod c\times i+b \bmod c}{c} \right \rfloor，式子就变成了：

\begin{aligned} &\sum_{i=0}^{n}\left(\left\lfloor\frac{a}{c}\right\rfloor^{2} i^{2}+\left\lfloor\frac{b}{c}\right\rfloor^{2}+t^{2}+2\left\lfloor\frac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor i+2\left\lfloor\frac{a}{c}\right\rfloor i t+2\left\lfloor\frac{b}{c}\right\rfloor t\right) \\ =&\sum_{i=0}^{n}\left\lfloor\frac{a}{c}\right\rfloor^{2} i^{2}+\sum_{i=0}^{n}\left\lfloor\frac{b}{c}\right\rfloor^{2}+\sum_{i=0}^{n} t^{2}+\sum_{i=0}^{n} 2\left\lfloor\frac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor i+\sum_{i=0}^{n} 2\left\lfloor\frac{a}{c}\right\rfloor i t+\sum_{i=0}^{n} 2\left\lfloor\frac{b}{c}\right\rfloor t \\ \end{aligned}

这个式子只是项数多，整理一下得到

\begin{aligned} G(a, b, c, n)&=G(a \bmod c, b \bmod c, c, n)+2\left\lfloor\frac{a}{c}\right\rfloor 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) \\ &+(n+1)\left\lfloor\frac{b}{c}\right\rfloor^{2}+\left\lfloor\frac{a}{c}\right\rfloor^{2} \frac{n(n+1)(2 n+1)}{6}+\left\lfloor\frac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor n(n+1) \\ \end{aligned}

所以，它会调用另外的两个函数，并且会一直递归。

(a<c) \wedge(b<c)

如果我们像之前一样换枚举，很难对付平方。可以用一种十分巧妙的方法来绕过它：

\begin{aligned} &n^2\\ =&(n^2+n)-n\\ =&2\times\frac{n(n+1)}{2}-n\\ =&\left(2\sum^{n}_{i=1} i\right )-n \end{aligned}

这样问题就简单很多了。

\begin{aligned} &G(a, b, c, n)\\ =&\sum_{i=0}^{n}\left(2 \sum_{j=1}^{\left\lfloor\frac{a i+b}{c}\right\rfloor} j-\left\lfloor\frac{a i+b}{c}\right\rfloor\right) \\ =&2 \sum_{i=0}^{n} \sum_{j=0}^{\left\lfloor \frac{a i+b}{c}\right\rfloor -1}(j+1)-F(a, b, c, n) \\ \end{aligned}

对于前一项，依旧用老方法换枚举。这样左边就是

2 \sum_{j=0}^{m-1}(j+1) \sum_{i=0}^{n}\left[j<\left\lfloor\frac{a i+b}{c}\right\rfloor\right] \\

不等式变换和上面一样。

\begin{aligned} &2 \sum_{j=0}^{m-1}(j+1) \sum_{i=0}^{n}\left[i>\left\lfloor\frac{j c+c-b-1}{a}\right\rfloor\right] \\ =&2 \sum_{j=0}^{m-1}(j+1)\left(n-\left\lfloor\frac{j c+c-b-1}{a}\right\rfloor\right) \\ =&2 \sum_{i=0}^{m-1}\left(n i+n-i\left\lfloor\frac{c i+c-b-1}{a}\right\rfloor-\left\lfloor\frac{c i-c-b-1}{a}\right\rfloor\right) \\ =&n m(m+1)-2 H(c, c-b-1, a, m-1)-2 F(c, c-b-1, a, m-1) \\ \end{aligned}

边界情况

很显然，如果 a=0，那结果就是 (n+1)\left \lfloor \frac{b}{c} \right \rfloor ^2。如果 n=0，那就是 \left \lfloor \frac{b}{c} \right \rfloor^2。

总结

G(a, b, c, n) =\left\{\begin{array}{c} (n+1)\left\lfloor\frac{b}{c}\right\rfloor^{2} &a=0 \\ \left\lfloor\frac{b}{c}\right\rfloor^{2} &n=0 \\ n m(m+1)-2 H(c, c-b-1, a, m-1)-2 F(c, c-b-1, a, m-1)-F(a, b, c, n) &a<c \wedge b<c \\ G(a \bmod c, b \bmod c, c, n)+2\left\lfloor\frac{a}{c}\right\rfloor 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)+\\ (n+1)\left\lfloor\frac{b}{c}\right\rfloor^{2}+\left\lfloor\frac{a}{c}\right\rfloor^{2} \frac{n(n+1)(2 n+1)}{6}+\left\lfloor\frac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor n(n+1) &a \geq c \vee b \geq c\\ \end{array}\right.

第三问

依旧分类讨论。

(a \ge c )\vee(b \ge c)

与之前类似，还是一样的操作。

\begin{aligned} &H(a, b, c, n)=\sum_{i=0}^{n} i\left|\frac{a i+b}{c}\right| \\ =&\sum_{i=0}^{n} i\left[\frac{\left(a \bmod c+\left\lfloor\frac{a}{c}\right\rfloor c\right) i+\left(b \bmod c+\left\lfloor\frac{b}{c}\right\rfloor c\right)}{c}\right] \\ =&\sum_{i=0}^{n} i\left|\frac{(a \bmod c) i+(b \bmod c)}{c}+i\right| \frac{a}{c}\left|+\left|\frac{b}{c}\right|\right| \\ =&\sum_{i=0}^{n} i\left|\frac{(a \bmod c) i+(b \bmod c)}{c}\right|+\sum_{i=0}^{n} i^{2}\left\lfloor\frac{a}{c}\right\rfloor+\sum_{i=0}^{n} i\left|\frac{b}{c}\right| \\ =&H(a \bmod c, b \bmod c, c, n)+\frac{n(n+1)(2 n+1)}{6}\left\lfloor\frac{a}{c}\right\rfloor+\frac{n(n+1)}{2}\left\lfloor\frac{b}{c}\right\rfloor \\ \end{aligned}

(a<c) \wedge(b<c)

$$ \begin{aligned} &H(a,b,c,n)\\ =&\sum_{i=0}^{n} i\left|\frac{a i+b}{c}\right| \\ =&\sum_{i=0}^{n} i \sum_{j=0}^{\left\lfloor\left.\frac{ai+b}{c}\right|-1\right.} 1 \\ =&\sum_{j=0}^{m-1} \sum_{i=0}^{n}i\left[ j<\left \lfloor \frac{ai+b}{c} \right \rfloor \right]\\ =&\sum_{j=0}^{m-1} \sum_{i=0}^{n} i\left[i>\left[\frac{j c+(c-b-1)}{a}\right]\right] \\ \end{aligned} $$ 不等式的变换也和前面相同。令 $t=\left \lfloor \frac{jc+c-b-1}{a} \right \rfloor$，那么 $$ \begin{aligned} &H(a, b, c, n)\\ =&\sum_{j=0}^{m-1} \sum_{i=0}^{n} i[i>t] \\ =&\sum_{j=0}^{m-1} \sum_{i=t+1}^{n} i \\ =&\sum_{j=0}^{m-1} \frac{(n-t)(n+t+1)}{2} \\ =&\frac{1}{2} \sum_{j=0}^{m-1}\left(n(n+1)-t^{2}-t\right) \\ =&\frac{1}{2}\left(m n(n+1)-\sum_{i=0}^{m-1} t^{2}-\sum_{i=0}^{m-1} t\right) \\ \end{aligned} $$ 接着把 $t$ 展开。注意 $j$ 改名了，展开时不要忘记改名。 $$ \begin{aligned} &\frac{1}{2}\left(m n(n+1)-\sum_{i=0}^{m-1}\left\lfloor\left.\frac{c i+c-b-1}{a}\right|^{2}-\sum_{i=0}^{m-1}\left\lfloor\frac{c i+c-b-1}{a}\right\rfloor\right)\right. \\ =&\frac{1}{2}(mn(n+1)-G(c, c-b-1, a, m-1)-F(c, c-b-1, a, m-1)) \\ \end{aligned} $$ 于是我们发现，这个 $H$ 函数又一次调用了前面的函数。 ## 边界情况 边界情况比较好考虑。如果 $n=0$，原式显然为 $0$；如果 $a=0$，原式显然为 $\frac{n(n+1)}{2}\left\lfloor\frac{b}{c}\right\rfloor$。 ## 总结 下面是函数 $H$ 的公式： $$ \begin{aligned} H(a, b, c, n) =\left\{\begin{array}{c} 0 &n=0 \\ \frac{n(n+1)}{2}\left\lfloor\frac{b}{c}\right\rfloor&a=0 \\ H(a \bmod c, b \bmod c, c, n)+\frac{n(n+1)(2 n+1)}{6}\left\lfloor\frac{a}{c}\right\rfloor +\frac{n(n+1)}{2}\left\lfloor \frac{b}{c}\right\rfloor & (a \geq c) \vee (b \geq c) \\ \frac{1}{2}(m n(n+1)-G(c, c-b-1,a, m-1)-F(c, c-b-1, a, m-1))& (a<c) \wedge (b<c) \end{array}\right. \end{aligned} $$ # 代码 代码的细节比较多，所以仔细说一下。 首先，题目让把答案取模，所以代码中除以 $2$ 和 $6$ 的部分应该乘它们的逆元。