来源

类欧几里德算法由洪华敦大佬在 2016 年 NOI\text{NOI} 冬令营营员交流中提出，其本质可以理解为，一个类似辗转相除法的函数求和的过程。截止 2020 年 4 月 29 日，百度百科和维基百科都尚未收录该词条 Orz\text{Orz}。

前置知识

取整函数

⌊ab⌋\left\lfloor\frac{a}{b}\right\rfloor 为 ab\frac{a}{b} 向下取整，⌈ab⌉\left\lceil\frac{a}{b}\right\rceil 为 ab\frac{a}{b} 向上取整。
基与下面的类欧几里得算法的推导过程，需要掌握一些取整函数的技巧。

⌊ab⌋⩾c⇔a⩾bc   ⌈ab⌉⩽c⇔a⩽bc   ⌊ab⌋<c⇔a<bc   ⌈ab⌉>c⇔a>bc\left\lfloor\frac{a}{b}\right\rfloor\geqslant c \Leftrightarrow a\geqslant bc\ \ \ \left\lceil\frac{a}{b}\right\rceil\leqslant c \Leftrightarrow a\leqslant bc\ \ \ \left\lfloor\frac{a}{b}\right\rfloor< c \Leftrightarrow a< bc\ \ \ \left\lceil\frac{a}{b}\right\rceil> c \Leftrightarrow a> bc

⌊ab⌋=⌈a+b+1b⌉   ⌈ab⌉=⌊a+b−1b⌋\left\lfloor\frac{a}{b}\right\rfloor=\left\lceil\frac{a+b+1}{b}\right\rceil\ \ \ \left\lceil\frac{a}{b}\right\rceil=\left\lfloor\frac{a+b-1}{b}\right\rfloor

证明要略

当 a mod b=0a\bmod b=0 时，上述式子显然都成立；当 a mod b≠0a\bmod b\ne 0 时，可以令 a=kb+ma=kb+m ，其中 k,m∈N∗k,m\in N^*，1⩽m<b1\leqslant m<b，可以轻易得到证明。

引入

类欧几里得算法主要用来计算形如 ∑i=0n⌊ai+bc⌋\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor，∑i=0ni⌊ai+bc⌋\sum\limits_{i=0}^n i\left\lfloor\frac{ai+b}{c}\right\rfloor，∑i=0n⌊ai+bc⌋2\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2的表达式。
记 f(a,b,c,n)=∑i=0n⌊ai+bc⌋f(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor，g(a,b,c,n)=∑i=0ni⌊ai+bc⌋g(a,b,c,n)=\sum\limits_{i=0}^n i\left\lfloor\frac{ai+b}{c}\right\rfloor，h(a,b,c,n)=∑i=0n⌊ai+bc⌋2h(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2。
其结果由递归函数得到。
由于推导过程类似欧几里得算法，时间复杂度同欧几里得算法一样也是 log⁡n\log n ，故称类欧几里得算法。

推导

推导 f(a,b,c,n)f(a,b,c,n)

f(a,b,c,n)f(a,b,c,n) 的形式最为简单，也最常出现；其几何意义为直角坐标系下，直线 y=ax+bcy=\frac{ax+b}{c} 与 x,yx,y 两轴包围区域内的整点个数。
当 a⩾ca\geqslant c 或 b⩾cb\geqslant c时，意味着可以将 a,ba,b 对 cc 取模简化问题。
当 a⩾ca\geqslant c 或 b⩾cb\geqslant c时

f(a,b,c,n)=∑i=0n⌊ai+bc⌋=∑i=0n⌊(⌊ac⌋c+a mod c)i+(⌊bc⌋c+b mod c)c⌋=∑i=0n[⌊ac⌋i+⌊bc⌋+⌊(a mod c)i+(b mod c)c⌋]=∑i=0n(⌊ac⌋i+⌊bc⌋)+∑i=0n⌊(a mod c)i+(b mod c)c⌋=n(n+1)2⌊ac⌋+(n+1)⌊bc⌋+f(a mod c,b mod c,c,n)\begin{split}f(a,b,c,n)&=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\\&=\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 \\&=\sum\limits_{i=0}^n\left[\left\lfloor\frac{a}{c}\right\rfloor i+\left\lfloor\frac{b}{c}\right\rfloor+\left\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\right\rfloor\right]\\&=\sum\limits_{i=0}^n\left(\left\lfloor\frac{a}{c}\right\rfloor i+\left\lfloor\frac{b}{c}\right\rfloor\right)+\sum\limits_{i=0}^n\left\lfloor\frac{(a\bmod c)i+(b\bmod c)}{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)\end{split}

那么问题就转化为 a<ca<c 且 b<cb<c 的情况。我们观察式子，发现只有 ii 这一个变量，因此就只能从 ii 下手。在推求和式时有一个常见的技巧，就是条件与贡献的放缩与转化。具体地说，在原式 f(a,b,c,n)=∑i=0n⌊ai+bc⌋f(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor 中， 0⩽i⩽n0\leqslant i\leqslant n 是条件，而 ⌊ai+bc⌋\left\lfloor\frac{ai+b}{c}\right\rfloor 是对总和的贡献。要加快一个求和式的计算，所有的方法都可以都可以归约为 贡献合并计算。如果发现式子的贡献难以合并，就可以将贡献与条件作转化得到另一个形式的求和式。

请阁下看好接下来的神仙操作！ Orz\text{Orz}

f(a,b,c,n)=∑i=0n⌊ai+bc⌋=∑i=0n∑j=1⌊ai+bc⌋1f(a,b,c,n)=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor=\sum\limits_{i=0}^n\sum\limits_{j=1}^{\left\lfloor\frac{ai+b}{c}\right\rfloor}1

当 a<ca<c 且 b<cb<c 时

f(a,b,c,n)=∑i=0n⌊ai+bc⌋=∑i=0n∑j=1⌊ai+bc⌋1=∑i=0n∑j=1⌊an+bc⌋[⌊ai+bc⌋⩾j]=∑j=1⌊an+bc⌋∑i=0n[⌊ai+bc⌋⩾j]=∑j=1⌊an+bc⌋∑i=0n[ai+b⩾cj]=∑j=1⌊an+bc⌋∑i=0n[i⩾⌈cj−ba⌉]=∑j=1⌊an+bc⌋∑i=⌈cj−ba⌉n1=∑j=1⌊an+bc⌋(n−⌈cj−ba⌉+1)=∑j=1⌊an+bc⌋(n−⌊cj+a−b−1a⌋+1)=n⌊an+bc⌋−∑j=1⌊an+bc⌋(⌊cj+a−b−1a⌋−1)=n⌊an+bc⌋−∑j=1⌊an+bc⌋⌊cj−b−1a⌋=n⌊an+bc⌋−∑j=0⌊an+bc⌋−1⌊c(j+1)−b−1a⌋=n⌊an+bc⌋−∑j=0⌊an+bc⌋−1⌊cj+c−b−1a⌋=n⌊an+bc⌋−f(c,c−b−1,a,⌊an+bc⌋−1)\begin{aligned} f(a,b,c,n)&=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\\&=\sum\limits_{i=0}^n\sum\limits_{j=1}^{\left\lfloor\frac{ai+b}{c}\right\rfloor}1\\&=\sum\limits_{i=0}^n\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\left[\left\lfloor\frac{ai+b}{c}\right\rfloor\geqslant j\right]\\&=\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\sum\limits_{i=0}^n\left[\left\lfloor\frac{ai+b}{c}\right\rfloor\geqslant j\right]\\&=\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\sum\limits_{i=0}^n\left[ai+b\geqslant cj\right]\\&=\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\sum\limits_{i=0}^n\left[i\geqslant \left\lceil \frac{cj-b}{a}\right\rceil\right]\\&=\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\sum\limits_{i=\left\lceil \frac{cj-b}{a}\right\rceil}^n1\\&=\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\left(n-\left\lceil \frac{cj-b}{a}\right\rceil+1\right)\\&=\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\left(n-\left\lfloor \frac{cj+a-b-1}{a}\right\rfloor+1\right)\\&=n\left\lfloor\frac{an+b}{c}\right\rfloor-\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\left(\left\lfloor \frac{cj+a-b-1}{a}\right\rfloor-1\right)\\&=n\left\lfloor\frac{an+b}{c}\right\rfloor-\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\left\lfloor \frac{cj-b-1}{a}\right\rfloor\\&=n\left\lfloor\frac{an+b}{c}\right\rfloor-\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left\lfloor \frac{c(j+1)-b-1}{a}\right\rfloor\\&=n\left\lfloor\frac{an+b}{c}\right\rfloor-\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left\lfloor \frac{cj+c-b-1}{a}\right\rfloor\\&=n\left\lfloor\frac{an+b}{c}\right\rfloor-f\left(c,c-b-1,a,\left\lfloor\frac{an+b}{c}\right\rfloor-1\right)\end{aligned}

边界条件为，当 a=0a=0 时，fa,b,c,n)=(n+1)⌊bc⌋fa,b,c,n)=(n+1)\left\lfloor\frac{b}{c}\right\rfloor。

推导 g(a,b,c,n)g(a,b,c,n)

当 a⩾ca\geqslant c 或 b⩾cb\geqslant c 时

g(a,b,c,n)=∑i=0ni⌊ai+bc⌋=∑i=0ni[⌊(a mod c)i+(b mod c)c⌋+⌊ac⌋i+⌊bc⌋]=∑i=0ni⌊(a mod c)i+(b mod c)c⌋+∑i=0n⌊ac⌋i2+∑i=0n⌊bc⌋i=n(n+1)(2n+1)6⌊ac⌋+n(n+1)2⌊bc⌋+∑i=0ni⌊(a mod c)i+(b mod c)c⌋=n(n+1)(2n+1)6⌊ac⌋+n(n+1)2⌊bc⌋+g(a mod c,b mod c,c,n)\begin{aligned}g(a,b,c,n)&=\sum\limits_{i=0}^n i\left\lfloor\frac{ai+b}{c}\right\rfloor\\&=\sum\limits_{i=0}^ni\left[\left\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\right\rfloor+\left\lfloor\frac{a}{c}\right\rfloor i+\left\lfloor\frac{b}{c}\right\rfloor\right]\\&=\sum\limits_{i=0}^n i\left\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\right\rfloor+\sum\limits_{i=0}^n\left\lfloor\frac{a}{c}\right\rfloor i^2+\sum\limits_{i=0}^n\left\lfloor\frac{b}{c}\right\rfloor i\\&=\frac{n(n+1)(2n+1)}{6}\left\lfloor\frac{a}{c}\right\rfloor+\frac{n(n+1)}{2}\left\lfloor\frac{b}{c}\right\rfloor+\sum\limits_{i=0}^n i\left\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\right\rfloor\\&=\frac{n(n+1)(2n+1)}{6}\left\lfloor\frac{a}{c}\right\rfloor+\frac{n(n+1)}{2}\left\lfloor\frac{b}{c}\right\rfloor+g(a\bmod c,b\bmod c,c,n)\end{aligned}

当 a<ca<c 且 b<cb<c 时

g(a,b,c,n)=∑i=0ni⌊ai+bc⌋=∑i=0n∑j=1⌊ai+bc⌋i=∑i=0n∑j=1⌊an+bc⌋i[⌊ai+bc⌋⩾j]=∑i=0n∑j=1⌊an+bc⌋i[ai+b⩾cj]=∑i=0n∑j=1⌊an+bc⌋i[i⩾⌈cj−ba⌉]=∑i=0n∑j=1⌊an+bc⌋i[i⩾⌊cj+a−b−1a⌋]=∑j=1⌊an+bc⌋∑i=0ni[i⩾⌊cj+a−b−1a⌋]=∑j=1⌊an+bc⌋∑i=⌊cj+a−b−1a⌋ni=∑j=1⌊an+bc⌋(n+⌊cj+a−b−1a⌋)(n−⌊cj+a−b−1a⌋+1)2=∑j=1⌊an+bc⌋(n+⌊cj−b−1a⌋+1)(n−⌊cj−b−1a⌋)2=∑j=0⌊an+bc⌋−1(n+⌊c(j+1)−b−1a⌋+1)(n−⌊c(j+1)−b−1a⌋)2=∑j=0⌊an+bc⌋−1(n+⌊cj+c−b−1a⌋+1)(n−⌊cj+c−b−1a⌋)2=12∑j=0⌊an+bc⌋−1[n(n+1)−⌊cj+c−b−1a⌋−⌊cj+c−b−1a⌋2]=12[∑j=0⌊an+bc⌋−1n(n+1)−∑j=0⌊an+bc⌋−1⌊cj+c−b−1a⌋−∑j=0⌊an+bc⌋−1⌊cj+c−b−1a⌋2]=12[⌊an+bc⌋n(n+1)−f(c,c−b−1,a,⌊an+bc⌋−1)−h(c,c−b−1,a,⌊an+bc⌋−1)]\begin{aligned}g(a,b,c,n)&=\sum\limits_{i=0}^n i\left\lfloor\frac{ai+b}{c}\right\rfloor\\&=\sum\limits_{i=0}^n\sum\limits_{j=1}^{\left\lfloor\frac{ai+b}{c}\right\rfloor} i\\&=\sum\limits_{i=0}^n\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor} i\left[\left\lfloor\frac{ai+b}{c}\right\rfloor\geqslant j\right]\\&=\sum\limits_{i=0}^n\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor} i\left[ai+b \geqslant cj\right]\\&=\sum\limits_{i=0}^n\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor} i\left[i\geqslant\left\lceil\frac{cj-b}{a}\right\rceil\right]\\&=\sum\limits_{i=0}^n\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor} i\left[i\geqslant\left\lfloor\frac{cj+a-b-1}{a}\right\rfloor\right]\\&=\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\sum\limits_{i=0}^n i\left[i\geqslant\left\lfloor\frac{cj+a-b-1}{a}\right\rfloor\right]\\&=\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor} \sum_{i=\left\lfloor\frac{cj+a-b-1}{a}\right\rfloor}^n i\\&=\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\frac{\left(n+\left\lfloor\frac{cj+a-b-1}{a}\right\rfloor\right)\left(n-\left\lfloor\frac{cj+a-b-1}{a}\right\rfloor+1\right)}{2}\\&=\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\frac{\left(n+\left\lfloor\frac{cj-b-1}{a}\right\rfloor+1\right)\left(n-\left\lfloor\frac{cj-b-1}{a}\right\rfloor\right)}{2}\\&=\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\frac{\left(n+\left\lfloor\frac{c(j+1)-b-1}{a}\right\rfloor+1\right)\left(n-\left\lfloor\frac{c(j+1)-b-1}{a}\right\rfloor\right)}{2}\\&=\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\frac{\left(n+\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor+1\right)\left(n-\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor\right)}{2}\\&=\frac{1}{2}\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left[n(n+1)-\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor-\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor^2\right]\\&=\frac{1}{2}\left[\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}n(n+1)-\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor-\sum\limits_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor^2\right]\\&=\frac{1}{2}\left[\left\lfloor\frac{an+b}{c}\right\rfloor n(n+1)-f\left(c,c-b-1,a,\left\lfloor\frac{an+b}{c}\right\rfloor-1\right)-h\left(c,c-b-1,a,\left\lfloor\frac{an+b}{c}\right\rfloor-1\right)\right]\end{aligned}

边界条件为，当 a=0a=0 时，g(a,b,c,n)=n(n+1)2⌊bc⌋g(a,b,c,n)=\frac{n(n+1)}{2}\left\lfloor\frac{b}{c}\right\rfloor 。

推导 h(a,b,c,n)h(a,b,c,n)

当 a⩾ca\geqslant c 或 b⩾cb\geqslant c 时

h(a,b,c,n)=∑i=0n⌊ai+bc⌋2=∑i=0n[⌊(a mod c)i+(b mod c)c⌋+⌊ac⌋i+⌊bc⌋]2=∑i=0n⌊(a mod c)i+(b mod c)c⌋2+∑i=0n⌊ac⌋2i2+∑i=0n⌊bc⌋2+2⌊ac⌋∑i=0n⌊(a mod c)i+(b mod c)c⌋i+2⌊bc⌋∑i=0n⌊(a mod c)i+(b mod c)c⌋+2⌊ac⌋⌊bc⌋∑i=0ni=h(a mod c,b mod c,c,n)+2⌊ac⌋g(a mod c,b mod c,c,n)+2⌊bc⌋f(a mod c,b mod c,c,n)+n(n+1)(2n+1)6⌊ac⌋2+(n+1)⌊bc⌋2+n(n+1)⌊ac⌋⌊bc⌋\begin{aligned}h(a,b,c,n)&=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2\\&=\sum\limits_{i=0}^n\left[\left\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\right\rfloor+\left\lfloor\frac{a}{c}\right\rfloor i+\left\lfloor\frac{b}{c}\right\rfloor\right]^2\\&=\sum\limits_{i=0}^n\left\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\right\rfloor^2+\sum\limits_{i=0}^n\left\lfloor\frac{a}{c}\right\rfloor^2i^2+\sum\limits_{i=0}^n\left\lfloor\frac{b}{c}\right\rfloor^2\\&+2\left\lfloor\frac{a}{c}\right\rfloor\sum\limits_{i=0}^n\left\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\right\rfloor i+2\left\lfloor\frac{b}{c}\right\rfloor\sum\limits_{i=0}^n\left\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\right\rfloor+2\left\lfloor\frac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor\sum\limits_{i=0}^n i\\&=h(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)+2\left\lfloor\frac{b}{c}\right\rfloor f(a\bmod c,b\bmod c,c,n)\\&+\frac{n(n+1)(2n+1)}{6}\left\lfloor\frac{a}{c}\right\rfloor^2+(n+1)\left\lfloor\frac{b}{c}\right\rfloor^2+n(n+1)\left\lfloor\frac{a}{c}\right\rfloor\left\lfloor\frac{b}{c}\right\rfloor\end{aligned}

当 a<ca<c 且 b<cb<c 时
∀x∈N+{\forall} x\in N^+，有如下骚操作 x2=2×x(x+1)2−x=2∑i=1xi−xx^2=2\times \frac{x(x+1)}{2}-x=2\sum\limits_{i=1}^xi -x

h(a,b,c,n)=∑i=0n⌊ai+bc⌋2=∑i=0n(2∑j=1⌊ai+bc⌋j−⌊ai+bc⌋)=2∑i=0n∑j=1⌊ai+bc⌋j−∑i=0n⌊ai+bc⌋=2∑i=0n∑j=1⌊an+bc⌋j[⌊ai+bc⌋⩾j]−∑i=0n⌊ai+bc⌋=2∑i=0n∑j=1⌊an+bc⌋j[ai+b⩾cj]−∑i=0n⌊ai+bc⌋=2∑i=0n∑j=1⌊an+bc⌋j[i⩾⌈cj−ba⌉]−∑i=0n⌊ai+bc⌋=2∑j=1⌊an+bc⌋j∑i=0n[i⩾⌈cj−ba⌉]−∑i=0n⌊ai+bc⌋=2∑j=1⌊an+bc⌋j∑i=0n[i⩾⌊cj+a−b−1a⌋]−∑i=0n⌊ai+bc⌋=2∑j=1⌊an+bc⌋[j(n−⌊cj+a−b−1a⌋+1)]−∑i=0n⌊ai+bc⌋=2∑j=1⌊an+bc⌋[j(n−⌊cj−b−1a⌋)]−∑i=0n⌊ai+bc⌋=2∑j=0⌊an+bc⌋−1[(j+1)(n−⌊c(j+1)−b−1a⌋)]−∑i=0n⌊ai+bc⌋=2∑j=0⌊an+bc⌋−1[(j+1)(n−⌊cj+c−b−1a⌋)]−∑i=0n⌊ai+bc⌋=2n∑j=0⌊an+bc⌋−1(j+1)−2∑j=0⌊an+bc⌋−1j⌊cj+c−b−1a⌋−2∑j=0⌊an+bc⌋−1⌊cj+c−b−1a⌋−∑i=0n⌊ai+bc⌋=⌊an+bc⌋(⌊an+bc⌋+1)n−2g(c,c−b−1,a,⌊an+bc⌋−1)−2f(c,c−b−1,a,⌊an+bc⌋−1)−f(a,b,c,n)\begin{aligned}h(a,b,c,n)&=\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor^2\\&=\sum\limits_{i=0}^n\left(2\sum\limits_{j=1}^{\left\lfloor\frac{ai+b}{c}\right\rfloor}j-\left\lfloor\frac{ai+b}{c}\right\rfloor\right)\\&=2\sum\limits_{i=0}^n\sum\limits_{j=1}^{\left\lfloor\frac{ai+b}{c}\right\rfloor}j-\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\\&=2\sum\limits_{i=0}^n\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}j\left[\left\lfloor\frac{ai+b}{c}\right\rfloor\geqslant j\right]-\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\\&=2\sum\limits_{i=0}^n\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}j\left[ai+b\geqslant cj\right]-\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\\&=2\sum\limits_{i=0}^n\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}j\left[i\geqslant\left\lceil\frac{cj-b}{a}\right\rceil\right]-\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\\&=2\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}j\sum\limits_{i=0}^{n}\left[i\geqslant\left\lceil\frac{cj-b}{a}\right\rceil\right]-\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\\&=2\sum\limits_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}j\sum\limits_{i=0}^{n}\left[i\geqslant\left\lfloor\frac{cj+a-b-1}{a}\right\rfloor\right]-\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\\&=2\sum_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\left[j\left(n-\left\lfloor\frac{cj+a-b-1}{a}\right\rfloor+1\right)\right]-\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\\&=2\sum_{j=1}^{\left\lfloor\frac{an+b}{c}\right\rfloor}\left[j\left(n-\left\lfloor\frac{cj-b-1}{a}\right\rfloor\right)\right]-\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\\&=2\sum_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left[(j+1)\left(n-\left\lfloor\frac{c(j+1)-b-1}{a}\right\rfloor\right)\right]-\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\\&=2\sum_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left[(j+1)\left(n-\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor\right)\right]-\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\\&=2n\sum_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}(j+1)-2\sum_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}j\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor-2\sum_{j=0}^{\left\lfloor\frac{an+b}{c}\right\rfloor-1}\left\lfloor\frac{cj+c-b-1}{a}\right\rfloor-\sum\limits_{i=0}^n\left\lfloor\frac{ai+b}{c}\right\rfloor\\&=\left\lfloor\frac{an+b}{c}\right\rfloor\left(\left\lfloor\frac{an+b}{c}\right\rfloor+1\right)n-2g\left(c,c-b-1,a,\left\lfloor\frac{an+b}{c}\right\rfloor-1\right)\\&-2f\left(c,c-b-1,a,\left\lfloor\frac{an+b}{c}\right\rfloor-1\right)-f(a,b,c,n)\end{aligned}

边界条件为，当 a=0a=0 时，h(a,b,c,n)=(n+1)⌊bc⌋2h(a,b,c,n)=(n+1)\left\lfloor\frac{b}{c}\right\rfloor^2

洛谷 P5170 【模板】类欧几里得算法 ↬\looparrowright

题目描述

给定 n,,a,b,cn,,a,b,c，分别求 ∑i=0n⌊ai+bc⌋,∑i=0n⌊ai+bc⌋2,∑i=0ni⌊ai+bc⌋\sum\limits_{i=0}^n\left\lfloor \frac{ai+b}{c} \right\rfloor, \sum\limits_{i=0}^n\left\lfloor \frac{ai+b}{c} \right\rfloor^2,\sum\limits_{i=0}^ni\left\lfloor \frac{ai+b}{c} \right\rfloor ，答案对 998244353998244353 取模。多组数据。

输入格式

第一行给出数据组数 tt 。
接下来 tt 行，每行有四个整数，分别为每组数据的 n,a,b,cn, a, b, c 。

输出格式

对于每组数据，输出一行三个整数，为三个答案对 998244353998244353 取模的结果。

输入输出样例

输入 #1

2
2 1 0 2
4 3 9 6

输出 #1

1 1 2
11 27 27

说明/提示

本题采用 Special Judge\mathrm{Special}\ \mathrm{Judge} 。
答对所有第一问可以获得测试点 40%40\% 的分数，答对所有第二问、第三问可以分别获得另外 30%30\% 的分数。

测试点编号 特殊性质
11 n,a,b,c⩽10n,a,b,c\leqslant 10
2∼32\sim3 n,a,b,c⩽100n,a,b,c\leqslant100
44 n,a,b,c⩽106n,a,b,c\leqslant10^6
55 t=1t=1
6∼106\sim10 无

对于所有测试点，有 1⩽t⩽105, 0⩽n,a,b,c⩽109,c≠01 \leqslant t \leqslant 10^5,\ 0 \leqslant n,a,b,c \leqslant 10^9, c \neq 0 。

分析

在计算的时侯，因为三个函数各有交错递归，因此可以考虑三个函数打包成结构体一起整体递归，同步计算，否则有很多项会被多次计算。
类欧几里得算法时间复杂度为 O(log⁡n)O(\log 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll mod=998244353;
/*-----2,6的乘法逆元-----*/
const ll inv2=499122177;
const ll inv6=166374059;
/*-----用快速幂得到------*/
/*ll quick_pow(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
int main()
{
	cout<<quick_pow(2,mod-2)<<endl;
	cout<<quick_pow(6,mod-2)<<endl;
	return 0;
}*/
struct A//将答案打包成结构体
{
	ll f;
	ll g;
	ll h;
};
A cal(ll a,ll b,ll c,ll n)//按照以上推得的公式进行递归
{
	A res,temp;
	if(!a)
	{
		res.f=(n+1)*(b/c)%mod;
		res.g=(b/c)*n%mod*(n+1)%mod*inv2%mod;
		res.h=(n+1)*(b/c)%mod*(b/c)%mod;
	}
	else if(a>=c||b>=c)
	{
		temp=cal(a%c,b%c,c,n);
		res.f=((a/c)*n%mod*(n+1)%mod*inv2%mod
		+(b/c)*(n+1)%mod+temp.f)%mod;
		res.g=((a/c)*n%mod*(n+1)%mod*(2*n+1)%mod*inv6%mod
		+(b/c)*n%mod*(n+1)%mod*inv2%mod+temp.g)%mod;
		res.h=((a/c)*(a/c)%mod*n%mod*(n+1)%mod*(2*n+1)%mod*inv6%mod
		+(b/c)*(b/c)%mod*(n+1)%mod+(a/c)*(b/c)%mod*n%mod*(n+1)%mod
		+temp.h+2*(a/c)%mod*temp.g+2*(b/c)%mod*temp.f)%mod;
	}
	else
	{
		ll m=(a*n+b)/c;
		temp=cal(c,c-b-1,a,m-1);
		res.f=(n*(m%mod)%mod-temp.f)%mod;
		res.g=(n*(n+1)%mod*(m%mod)%mod-temp.f-temp.h)%mod*inv2%mod;
		res.h=(n*(m%mod)%mod*((m+1)%mod)%mod-2*temp.g-2*temp.f-res.f)%mod;
	}
	return res;
}
int main()
{
	int _;
	for(cin>>_;_;_--)
	{
		ll n,a,b,c;
		scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
		A ans=cal(a,b,c,n);
		//注意负数的问题
		printf("%lld %lld %lld\n",(ans.f+mod)%mod,(ans.h+mod)%mod,(ans.g+mod)%mod);
	}
	return 0;
}