https://blog.csdn.net/tenkuo/article/details/158125076?spm=1001.2014.3001.5502

首先想偷懒写递归的劝你还是放弃吧。

如果觉得题解太石可以看这个：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ac (a/c)
#define bc (b/c)
#define gs(x) x*(x+1)%P*i2%P
#define gf(x) x*(x+1)%P*(2*x+1)%P*i6%P
const int P=998244353,i2=499122177,i6=166374059;
struct node{int f,g,h;};
node calc(int a,int b,int c,int n)
{
	node ans;
	if(a==0)
	{
		ans.f=bc*(n+1)%P;
		ans.g=bc*gs(n)%P;
		ans.h=bc*bc%P*(n+1)%P;
		return ans;
	}
	if(n==0)
	{
		ans.f=bc;
		ans.g=0;
		ans.h=bc*bc%P;
		return ans;
	}
	if(a>=c||b>=c)
	{
		node sum=calc(a%c,b%c,c,n);ans=sum;
		ans.f=(ans.f+gs(n)*ac%P+(n+1)*bc%P)%P;
		ans.g=(ans.g+gf(n)*ac%P+gs(n)*bc%P)%P;
		ans.h=(ans.h+gf(n)*ac%P*ac%P+(n+1)*bc*bc%P+n*(n+1)%P*ac%P*bc%P)%P;
		ans.h=(ans.h+2*ac%P*sum.g%P+2*bc%P*sum.f%P)%P;
		return ans;
	}
	int m=(a*n+b)/c;
	node sum=calc(c,c-b-1,a,m-1);
	ans.f=((n*m%P-sum.f)%P+P)%P;
	ans.g=((m*n%P*(n+1)%P-sum.h-sum.f)%P+P)%P;
	ans.g=(ans.g*i2)%P;
	ans.h=((n*m%P*(m+1)%P-2*sum.g%P-2*sum.f%P-ans.f)%P+P)%P;
	return ans;
}
signed main()
{
	int t;cin>>t;
	while(t--)
	{
		int a,b,c,n;cin>>n>>a>>b>>c;
		node res=calc(a,b,c,n);
		cout<<res.f<<' '<<res.h<<' '<<res.g<<'\n';
	}
	return 0;
}

类欧几里得算法

类欧还挺难的，但是很有意思，我尽量用最浅显的语言来描述，不懂得评论区提出。

那么，我们来学习一下最基本的类欧吧。

【提高】类欧几里得算法基础

更新日志

• 更新了函数中 $n$ 和 $d$ 混淆的情况。
• 增加了对谓词函数更加浅显的讲解。
• 修改了不等式部分一些不严谨的内容，更正错别字。
• 强调了一些易混淆的公式。
• 修改了部分细节。
• 更正了取余化简中的推导错误。
• 修正了贡献化简中引起歧义的符号问题。

所求大意

基本题意就是，给定 $a,b,c,n$，求：

$$\sum_{x=0}^{n}\left\lfloor\dfrac{ax+b}{c}\right\rfloor$$

以几何的角度来理解就是“求直线在给定区间下包含整点的个数”。

首先，将其写成普通函数的形式：

$$f(a,b,c,n)=\sum_{x=0}^{n}\left\lfloor\dfrac{ax+b}{c}\right\rfloor$$

那么我们接下来的任务就是化简了。

取模化简

化简意义：能够将 $a\ge c$ 或 $b\ge c$ 的情况转化为 $a,b<c$ 的情况。

首先我们可以将 $a$ 拆分为 $(a\bmod c)+(a-a\bmod c)$，同样，$b$ 也可这样处理，分为 $(b\bmod c)+(b-b\bmod c)$，这样，对于包含 $a$ 的这一项我们可以将 $x$ 提取出来，利用乘法分配律很容易得出：

$$f(a,b,c,n)=\sum_{x=0}^{n}\left\lfloor\dfrac{(a\bmod c)x+(a-a\bmod c)x+(b\bmod c)+(b-b\bmod c)}{c} \right\rfloor$$

这时候我们会发现要进一步化简其实很容易，因为我们知道对于任意的 $\dfrac{t_0+t_1}{t_2}=\dfrac{t_0}{t_2}+\dfrac{t_1}{t_2}$，所以我们可以对上述的柿子做同样的处理，将对 $c$ 取模的部分合并，同时将剩下的部分也合并：

$$f(a,b,c,n)=\sum_{x=0}^{n}\left\lfloor\dfrac{(a \bmod c)x + (b \bmod c)}{c}\right\rfloor+\dfrac{(a-a\bmod c)x}{c}+\dfrac{b-b \bmod c}{c}$$

注意，由于取余后剩下的部分一定能被 $c$ 整除，所以不需要加上下取整的括号，于是我们就能够成功的将其拆成几个部分。

这时思考一下，是否一定存在：

$$\left\lfloor\dfrac{a}{c}\right\rfloor=\dfrac{a-(a\bmod c)}{c}$$

事实上，这样的一个化简就是利用“下取整忽略余数部分”的一个思想，达成去掉取余符号的目的，那么对于 $a$ 和 $b$ 的相关柿子都进行类似的处理，我们就可以得到：

$$\sum_{x=0}^{n}\left\lfloor\dfrac{(a\bmod c)x+(b\bmod c)}{c}\right\rfloor+\left\lfloor\dfrac{a}{c}\right\rfloor x+\left\lfloor\dfrac{b}{c}\right\rfloor$$

对于那个含有 $a$ 的部分，由于存在 $x$（作为循环变量），我们可以用高斯求和公式得出其总和，同样的，对于不存在循环变量作为系数的 $b$ 相关柿子，我们也可以简单的化简为：

$$\left(\dfrac{n(n+1)}{2}\cdot\left\lfloor\dfrac{a}{c}\right\rfloor+n\left\lfloor\dfrac{b}{c}\right\rfloor \right)+\sum_{x=0}^{n}\left\lfloor\dfrac{(a\bmod c)x+(b\bmod c)}{c}\right\rfloor$$

然后我们再将其求和部分写成最初定义的基本函数形式：

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

这样的一个作用是我们能够将函数中 $a$ 和 $b$（注意，不是原式中的常量，而是右半部分函数的参数）写成 $a<c$ 且 $b<c$ 的形式（显然取模是保证了这一作用），那么我们就可以进行其他的操作了。

好的，我们的化简暂告一段落。

贡献化简

化简意义：形成“辗转相除”的形式，使得数量级递减，达到 $O(\log n)$ 的复杂度。

怎么说呢，接下来这一部分有些困难，一定要仔细理解。

我们很容易可以理解的一个想法是，对于：

$$\sum\limits_{x=0}^{n}\left\lfloor\dfrac{ax+b}{c}\right\rfloor$$

来说，$x\le n$ 是条件，而 $\left\lfloor\dfrac{ax+b}{c}\right\rfloor$ 是这个循环的贡献，他很容易就可以化简为这样的式子：

$$\left\lfloor\dfrac{ax+b}{c}\right\rfloor=1\cdot\left\lfloor\dfrac{ax+b}{c}\right\rfloor$$

那么我们不妨将他改为条件，而贡献用作 $1$，这样整理出来的式子如下：

$$\left\lfloor\dfrac{ax+b}{c}\right\rfloor=\sum\limits_{j=0}^{\left\lfloor\frac{ax+b}{c}\right\rfloor-1}1$$

之所以条件要减一，因为我们将循环变量从 $0$ 开始了，所以原式我们就可以简化为：

$$\sum\limits_{x=0}^{n}\sum\limits_{j=0}^{\left\lfloor\frac{ax+b}{c}\right\rfloor-1}1$$

大家可以发现一种神奇的现象，在 $j$ 的式子条件中，会改变的值只有 $x$ 一个，所以我们可以说“$x$ 限制了 $j$ 的上界”，而我们用类似的思想就可以看出来 $n$ 限定了 $x$ 的上界。

那么我们就可以用一种非常简单的办法来解决了，由于调换两个式子的顺序是不会影响他们的结果，所以我们可以通过调整顺序来使得 $x$ 和 $j$ 都被 $n$ 限制，这有利于我们后面继续化简：

$$\sum\limits_{j=0}^{\left\lfloor\frac{ax+b}{c}\right\rfloor-1}\sum\limits_{x=0}^{n}\left[j<\left\lfloor\dfrac{ax+b}{c}\right\rfloor\right]$$

注意，对于一个包含（类）逻辑表达式的中括号（如下）：

$$\left[j<\left\lfloor\dfrac{ax+b}{c}\right\rfloor\right]$$

当中括号内的逻辑式成立时，其值为 $1$，反之为 $0$，我们称其为的谓词函数，而这样的一个方式能让他在正确的时候做出正确的贡献（想一想，为什么），相当于限制了循环变量的范围。

不过还需要注意，外面是中括号，中间的括号是下取整符号，注意他们长相的差别。然后，我们可以利用不等式的一些独特特性，来对谓词函数内的柿子做一定简单的处理，如下：

$$j<\left\lfloor\dfrac{ax+b}{c}\right\rfloor$$

由于我们知道 $j$ 一定是整数，同时不等式的右半边由于下取整的符号存在，也一定是整数，那么我们就可以认为两边的差距至少为 $1$，由此可以推出：

$$j+1\le\left\lfloor\dfrac{ax+b}{c}\right\rfloor$$

由于下取整过后的结果一定小于等于原数，所以我们可以进一步去掉下取整符号：

$$j+1\le\dfrac{ax+b}{c}$$

接着，由于已知 $c$ 一定是正整数（注意存在正这个条件），所以两边同时乘 $c$ 得到：

$$cj+c\le ax+b$$

按照我们已经学过的不等式法则，一通变换易得：

$$cj+c-b\le ax\quad\to\quad cj+c-b-1<ax$$

最后，再次进行下取整就可以得到：

$$\left\lfloor\dfrac{cj+c-b-1}{a}\right\rfloor<x$$

这时候，我们利用不等式和下取整的一些特性，严格将 $x$ 消除（或者说减少了 $x$ 对于整个柿子的影响），所以之后的“限制”就可以直接用这个式子进行化简。

这时候，为了在之后的表达更为简便，我们引入新变量，令 $m=\left\lfloor\dfrac{ax+b}{c}\right\rfloor$，我们就可以继续化简：

$$f(a,b,c,n)=\sum\limits_{j=0}^{m-1}\sum\limits_{x=0}^{n}\left[x>\left\lfloor\dfrac{cj+c-b-1}{a}\right\rfloor\right]$$

这时候我们发现第二重求和是可以化简的，由于他的贡献简单，所以接着简化循环就可以写出来一个简单的式子（并且也把谓词函数消除了）：

$$f(a,b,c,n)=\sum\limits_{j=0}^{m-1}\left(n-\left\lfloor\dfrac{cj+c-b-1}{a}\right\rfloor\right)$$

我们把 $n$ 对整个式子的贡献单独拿出来，其他再算：

$$f(a,b,c,n)=n\cdot m - \sum\limits_{j=0}^{m-1}\left\lfloor\dfrac{cj+c-b-1}{a}\right\rfloor$$

那么，似乎不能再（或者说不必要）进一步简化柿子了，这时候我们仔细观察就能发现，最后一部分的柿子和我们一开始的定义有亿点点相似，那么能不能把他写成递归的形式呢？

我们再来看看定义：

$$f(a,b,c,n)=\sum_{x=0}^{n}\left\lfloor\dfrac{ax+b}{c}\right\rfloor$$

如果要写成基本柿子，那么必须要将两个柿子的元素对应起来。显然可以注意到的是，在这样的一个函数中存在的对应有：

• $m$ 对应原来的 $n$；
• $c$ 对应原来的 $a$；

如果我们将 $c-b-1$ 看成一个整体，那么还存在：

• $c-b-1$ 对应原来的 $b$；
• $a$ 对应原来的 $c$。

同样的，我们如果只对 $a$ 和 $c$ 进行观察，我们会发现他们的位置互换了。互换之后大小关系也就相反，如果再进行第一次的取膜化简，就容易将其数量级大大减小。那么，求和过程中的 $n$ 能不能拿出来计算呢？

第一部分的 $n$ 一共计算了 $m$ 次，即循环 $m$ 次每次贡献为 $n$，所以他对于整个柿子的贡献是 $n\cdot m$，而最后我们将后面的式子用函数的形式写出来就是：

$$f(a,b,c,d)=n\cdot m-f(c,c-b-1,a,m-1)$$

好的，我们已经将这样一个柿子进行了长足的化简，剩下的就只有实现了！那么我们应该怎样对一个普通的式子进行处理呢？事实上，我们必须要清楚，两种不同的化简并非随意使用，而是两种特定的情况下使用的，这样交替化简，就很容易根据我们已经证明过的内容得出：

• 如果存在 $a\ge c$ 或 $b\ge c$，进行取模化简的处理：

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

• 反之，进行第二次化简的处理：

$$f(a,b,c,d)=n\cdot m-f(c,c-b-1,a,m-1)$$

第一个柿子是对于 $a\ge c$ 或 $b\ge c$ 情况的化简，能使他变成第二个情况，好进行递归化简。

而正是这样的一个递归形式的式子，我们反复的递归调用就可以将 $c$ 和 $a$ 调换并缩小，从而一步步减少数量级，观察一下代码并做一个粗略的评估，可以感性地看出这个柿子可以用 $O(\log n)$ 的复杂度做到函数求和。

反复调换缩小数量级的过程，其实特别像求最大公约数的过程，也就是欧几里得算法（辗转相除法）：

$$\gcd(a,b)=\gcd(b,a \bmod b)$$

所以，这样的一个“求值过程类似于欧几里得算法的算法”，我们称之为“类欧几里得算法”。

就这样，我们完成了完整的推导。

代码实现

事实上，我们要注意一点：

• 如果存在 $a\ge c$ 或 $b\ge c$，就要将他们进行第一次取模化简的处理。
• 否则进行第二次化简的处理。

版本一：求的范围为 $1\sim n-1$

你会发现这个版本是在直接模拟我们第一次求出来的内容，同时将后半部分进行了替换，我是用它 AC 了“求不出的等式”一题。

然而这个式子也的确很迷惑，我也不大能理解，所以感性看看吧。

int f(int a,int b,int c,int n) {
    if(n<=0)return 0;
    return n*(n-1)/2*(a/c)+n*(b/c)+f(c,(a*n+b)%c,a%c,(a%c*n+b%c)/c);
}

版本二：正式模板

这个模板是正确的，且在多道题目都测试过了，应该没有问题。可以说是忠实的按照我们最后的推导来实现了。

int f(int a,int b,int c,int n){
	if(a==0)return((b/c)*(n+1));
	if(a>=c||b>=c)return f(a%c,b%c,c,n)+(a/c)*n*(n+1)/2+(b/c)*(n+1);
	int m=(a*n+b)/c;
	return n*m-f(c,c-b-1,a,m-1);
}

后记：我为什么写学习笔记

其实，我特别享受一个分享和总结的过程。

真正的学习是永无止境的，你的笔记可能真的没什么人看，可能写的粗糙，还可能有学术错误——但是这样一个不断完善、修改和重构的过程中，你才能更深入的对算法和知识有自己的理解，正如同你没有亲手打过调过 pushup 就不会深刻的知道线段树怎么实现；正如你没有一步步推导过欧拉恒等式的柿子，也不会知道他究竟为什么美，为什么那么有魅力；而学习笔记，正是自己的一本日记本，所有的心酸和快乐，都共存于此，这是一本属于 OI 的回忆录。

梦想路上，也不是所有的努力都会奏效，同样的，学习算法的过程中也不会总是一帆风顺。我想，走过这么多的坎坷，才能知道，无论算法还是自己，“为什么这样”，“怎么才可以这样”，“都将会怎么样”；也就是过去、现在和未来。

正所谓“在 OI 中，更重要的是怎样求的更快，而不是怎样求”，这样的一个推导的过程，与我来说是优美的，更像是一场盛宴，遇到困难和挫折，自己思考解决，和大家探讨——写学习笔记的过程，其实就像是和一个个算法约会，更深入他们的内心，才能成为一个合格的 OIer。

其实，我们的每一份努力，都不必存在理由。

---

最后，感谢大家的阅读，点个赞好吗？

且听鹤鸣于九皋：类欧几里得算法进阶

劝君平地上，还似过坡时。

去年⑨月的时候，我写了一篇类欧几里得算法的盛宴，在现在看来反响还不错，而现在的我也比那时强了那么一点，于是对于类欧的两种扩展形式，我们就可以着手研究了。当然还麻烦各位想要阅读这一篇文章的，确认自己已经基本明白第一篇的内容了，因为在这一篇的推导之中，我们会应用一部分上一篇的内容（从而使得推导更简单明了一些）。

相信有了第一篇的基础，第二篇会理解起来更容易，那我们开始吧。

$g$ 函数的化简

现在需要化简的 $g$ 函数定义如下：

$$g(a,b,c,n)=\sum_{x=0}^{n}x\left\lfloor\dfrac{ai+b}{c}\right\rfloor$$

类似于第一篇中的取模，我们可以得到式子：

$$g(a,b,c,n)=\sum_{x=0}^{n}x\left\lfloor\dfrac{(a\bmod c)x+(a-a\bmod c)x+(b\bmod c)+(b-b\bmod c)}{c} \right\rfloor$$

先拆分开来，然后将系数进行单独的计算：

$$g(a,b,c,n)=\sum_{x=0}^{n}x\left\lfloor\dfrac{(a \bmod c)x + (b \bmod c)}{c}\right\rfloor+\dfrac{(a-a\bmod c)x^2}{c}+\dfrac{(b-b \bmod c)x}{c}$$

进一步进行单独化简，系数依然保留：

$$\sum_{x=0}^{n}x\left\lfloor\dfrac{(a\bmod c)x+(b\bmod c)}{c}\right\rfloor+\left\lfloor\dfrac{a}{c}\right\rfloor x^2+\left\lfloor\dfrac{b}{c}\right\rfloor x$$

你会发现后两项的系数可以应用求和公式来计算，这里给出简单的说明：

$$\sum\limits_{x=0}^{n}x^2=\sum\limits_{x=1}^{n}x^2= 1^2+2^2+3^2+\cdots+n^2$$$$\sum\limits_{x=1}^{n}x^2=\sum\limits_{x=1}^{n}x(x+1)-x$$

考虑 $x(x+1)=\dfrac{x(x+1)(x+2)-(x-1)x(x+1)}{3}$ 我们可以进行一步伸缩求和，你会发现后半部分是可以消掉的。

于是结果就变成了 $\dfrac{n(n+1)(n+2)}{3}$，然后减去的 $x$ 可以用高斯求和化作 $\dfrac{n(n+1)}{2}$。

原式变成 $\dfrac{n(n+1)(n+2)}{3}-\dfrac{n(n+1)}{2}=\dfrac{n(n+1)(2n+1)}{6}$。

那我们就可以写出来：

$$\sum_{x=0}^{n}\left(\left\lfloor\dfrac{a}{c}\right\rfloor x^2+\left\lfloor\dfrac{b}{c}\right\rfloor x\right)=\dfrac{n(n+1)(2n+1)}{6}\left\lfloor\dfrac{a}{c}\right\rfloor+\dfrac{n(n+1)}{2}\left\lfloor\dfrac{b}{c}\right\rfloor$$

剩下这部分是我们熟悉的，可以写成基础形式：

$$\sum_{x=0}^{n}x\left\lfloor\dfrac{(a\bmod c)x+(b\bmod c)}{c}\right\rfloor$$

简单地合并起来，就是这个式子了：

$$g(a,b,c,n)=g(a\bmod c,b\bmod c,c,n)+\left\lfloor{\dfrac{a}{c}}\right\rfloor\dfrac{n(n+1)(2n+1)}{6}+\left\lfloor{\dfrac{b}{c}}\right\rfloor\dfrac{n(n+1)}{2}$$

此时，我们已经将原有的的式子化成了一个 $a,b<c$ 的情况，而我们可以进一步进行化简了：

令 $m=\left\lfloor{\dfrac{an+b}{c}}\right\rfloor$，我们回顾一下之前化简过程中的一个柿子：

$$f(a,b,c,n)=\sum\limits_{j=0}^{\left\lfloor\frac{ax+b}{c}\right\rfloor-1}\sum\limits_{x=0}^{n}\left[j<\left\lfloor\dfrac{ax+b}{c}\right\rfloor\right]$$

把 $m$ 代入就是：

$$f(a,b,c,n)=\sum\limits_{j=0}^{m-1}\sum\limits_{x=0}^{n}\left[j<\left\lfloor\dfrac{ax+b}{c}\right\rfloor\right]$$

谓词函数之内的一些内容可以单独化简，对于 $g$ 函数来说也是如此，这时候我们唯一需要的是加上 $g$ 和 $f$ 之前差的哪一个系数：

$$g(a,b,c,n)=\sum\limits_{j=0}^{m-1}\sum\limits_{x=0}^{n}\left[j<\left\lfloor\dfrac{ax+b}{c}\right\rfloor\right]\cdot x$$

同样地，我们之前的化简过程也有另一个式子：

$$f(a,b,c,n)=\sum\limits_{j=0}^{m-1}\sum\limits_{x=0}^{n}\left[x>\left\lfloor\dfrac{cj+c-b-1}{a}\right\rfloor\right]$$

想起来了吗？这个式子可以很容易地化简出结论。而对于我们当前的式子，同样多了一个系数 $x$，另外，这个式子看起来很杂乱，我们把一大堆变量的那一堆单独换元：

设 $t=\left\lfloor\dfrac{cj+c-b-1}{a}\right\rfloor$，代入原式得到：

$$g(a,b,c,n)=\sum\limits_{j=0}^{m-1}\sum\limits_{x=0}^{n}\left[x>t\right]\cdot x$$

细心观察的读者可能会注意到，$x$ 循环 $n$ 次的这个循环是可以解决的，我们单独把他拿出来看：

$$\sum\limits_{x=0}^{n}\left[x>t\right]\cdot x$$

容易发现，当 $x\le t$ 的时候该式子值为 $0$，那么我们考虑从 $t+1$ 开始求，这样和式就不受到谓词函数的牵连：

$$\sum\limits_{x=t+1}^{n}x$$

诶，这个东西简单！这不就是等差数列吗？首项为 $t+1$，末项为 $n$，项数为 $n-(t+1)+1=n-t$，那么这个式子就化成了：

$$\sum\limits_{x=t+1}^{n}x=\dfrac{(t+1+n)(n-t)}{2}$$

这是一个巨大的进步！代入原式，我们的式子就大大简化力，即：

$$g(a,b,c,n)=\sum\limits_{j=0}^{m-1}\dfrac{(t+1+n)(n-t)}{2}$$

诶，这个循环……好像这个 $j$ 在求和式子之中没有什么影响了诶……真的吗？并不。注意到之前换元的地方，他们是受到 $j$ 影响的，这似乎并不是什么好消息，但他依然意味着我们可以吧和 $t$ 无关的内容单独整出来：

$$\dfrac{(t+1+n)(n-t)}{2}=\dfrac{1}{2}\left(nt+n+n^2-t^2-t-nt\right)$$

合并一下同类项，就是：

$$\dfrac{1}{2}(n+n^2)-\dfrac{1}{2}(t^2+t)$$

好，这个 $\tfrac{1}{2}$ 看着很烦人，我们把它拿到求和式子的前面去，由于他和求和中循环变量的变化并没有什么关系，把他作为整个式子的系数并不会影响式子的值。并且，可以尝试着把我们化简的部分再次展开——和 $t$ 相关的放上循环式子，和 $t$ 不相关的用等差数列解决。

$$\dfrac{1}{2}\left(\sum\limits_{j=0}^{m-1}(n+n^2)-(t^2+t)\right)$$$$\dfrac{1}{2}\left(\sum\limits_{j=0}^{m-1}(n+n^2)\right)-\dfrac{1}{2}\left(\sum\limits_{j=0}^{m-1}(t^2+t)\right)$$

前半部分的 $n+n^2=n(n+1)$ 这是简单的初中数学，然后把 $m$ 这个循环次数作为系数乘进去（因为 $j$ 是从 $0$ 开始的），于是得到：

$$\dfrac{1}{2}\left(mn(n+1)-\sum\limits_{j=0}^{m-1}(t^2+t)\right)$$

到这里，有技术性的推导已经结束了，接下来需要做的只是对应，譬如：

$$\sum\limits_{j=0}^{m-1}(t^2+t)=\sum\limits_{j=0}^{m-1}t^2+\sum\limits_{j=0}^{m-1}t$$

诶，$t$ 是什么来着？$t=\left\lfloor\dfrac{cj+c-b-1}{a}\right\rfloor$，对应一下，得到：

$$\sum\limits_{j=0}^{m-1}t=\sum\limits_{j=0}^{m-1}\left\lfloor\dfrac{cj+c-b-1}{a}\right\rfloor=f(c,c-b-1,a,m-1)$$

看看这个式子，是不是这样？原式就变成了：

$$\dfrac{1}{2}\left(mn(n+1)-\sum\limits_{j=0}^{m-1}t^2-f(c,c-b-1,a,m-1)\right)$$

诶，中间那坨 $t^2$ 咋整呢？好像没有推导过？马上就会推导，我们姑且把他记为 $h(c,c-b-1,a,m-1)$，也就是我们要进行化简的下一个任务。

$g$ 函数的推导，也就暂告一段落。

$h$ 函数的化简

我们要处理的 $h$ 函数，完整的定义如下：

$$h(a,b,c,n)=\sum_{x=0}^{n}\left\lfloor \dfrac{ax+b}{c}\right\rfloor^2$$

对于新手来说，这玩意儿是真的烦，由于篇幅缘故，取模部分的推导我们不多赘述了（两个原因：作者推导过程中出现细节错误 和 本过程没有太多思维含量）。

我们可以推导出取模后的结果：

$$\begin{aligned}h(a,b,c,n)&=h(a\bmod c,b\bmod c,c,n)\\ &+2\left\lfloor\dfrac{b}{c}\right\rfloor f(a\bmod c,b\bmod c,c,n)+2\left\lfloor\dfrac{a}{c}\right\rfloor g(a\bmod c,b\bmod c,c,n)\\ &+\left\lfloor\dfrac{a}{c}\right\rfloor^2\dfrac{n(n+1)(2n+1)}{6}+\left\lfloor\dfrac{b}{c}\right\rfloor^2(n+1)+\left\lfloor\dfrac{a}{c}\right\rfloor\left\lfloor\dfrac{b}{c}\right\rfloor n(n+1)\end{aligned}$$

然后我们实际上已经确认了 $a<c,b<c$ 这一事实，接下来对于满足 $a<c,b<c$ 的式子 $h(a,b,c,n)$ 进行单独推导，前面那一大叠可以再最后整合时再使用（也就是说，我们在 $a,b\ge c$ 的时候需要用上面这一方法进行化简，但一旦化简之后就可以用普通的递归来解决了）。

回归定义：

$$h(a,b,c,n)=\sum_{x=0}^{n}\left\lfloor\dfrac{ax+b}{c}\right\rfloor^2$$

平方确实不太好处理，但是我们知道：

$$t^2=2\times\dfrac{t(t+1)}{2}-t=\left(2\sum\limits_{x=1}^{t}x\right)-t$$

于是我们可以将 $\left\lfloor \dfrac{ax+b}{c}\right\rfloor$ 当做前文推导中的那个 $t$，来进行剥离，也就是：

$$h(a,b,c,n)=\sum_{x=0}^{n}\left(2\!\!\sum\limits_{j=1}^{\left\lfloor\frac{ax+b}{c}\right\rfloor}j-\left\lfloor\dfrac{ax+b}{c}\right\rfloor\right)$$

接着我们把它再一次拆分，可以得到：

$$h(a,b,c,n)=2\sum_{x=0}^{n}\!\!\sum\limits_{j=1}^{\left\lfloor\frac{ax+b}{c}\right\rfloor}j-\sum_{x=0}^{n}\left\lfloor\dfrac{ax+b}{c}\right\rfloor$$

后半部分我们太熟悉了，就是 $f(a,b,c,n)$，通过这样我们拿掉了式子中烦人的平方，留下了一个求和式的嵌套，那么我们该怎么化简前一部分呢？

$$h(a,b,c,n)=2\sum_{x=0}^{n}\!\!\sum\limits_{j=1}^{\left\lfloor\frac{ax+b}{c}\right\rfloor}j-f(a,b,c,n)$$

类似于我们曾经推导的，我们设 $m=\left\lfloor\dfrac{ax+b}{c}\right\rfloor$，同时暂且不看系数（化简之后重新代回即可）：

$$\begin{aligned} \sum_{x=0}^{n} \sum \limits_{j=1}^{m}j&= \sum_{x=0}^{n} \sum \limits_{j=0}^{m-1}(j+1)\\&= \sum \limits_{j=0}^{m-1}(j+1) \sum \limits_{x=0}^{n} \bigg[\lfloor{j<m}\rfloor\bigg]\end{aligned}$$

目前已经用上熟悉的贡献求和与谓词函数，现在类似于之前，令 $t=\left\lfloor{\dfrac{jc+c-b-1}{a}}\right\rfloor$ 我们还可以用在化简 $f$ 与 $h$ 过程中推导过的结论进一步化简：

$$\sum_{x=0}^{n}\sum\limits_{j=1}^{m}j&=\sum\limits_{j=0}^{m-1}(j+1)\sum\limits_{x=0}^{n}\bigg[\lfloor{j<m}\rfloor\bigg]\\&=\sum\limits_{j=0}^{m-1}(j+1)\sum\limits_{x=0}^{n}[x>t]\cdot x\\&=\sum\limits_{j=0}^{m-1}(j+1)\dfrac{(t+n+1)(n-t)}{2}]$$

这时候不难发现，我们可以将已知的部分展开（都是推导过的结论了，这里直接写不解释）得到：

$$\dfrac{mn(n+1)-\sum\limits_{j=0}^{m-1}t^2-\sum\limits_{j=0}^{m-1}t}{2}=\dfrac{mn(n+1)-h(c,c-b-1,a,m-1-f(c,c-b-1,a,m-1))}{2}$$

于是我们进一步得到了化简的答案。

接着别忘了代回我们忘记很久的原式，得到：

$$h(a,b,c,n)=nm(m+1)-2g(c,c-b-1,a,m-1)-2f(c,c-b-1,a,m-1)-f(a,b,c,n)$$

好家伙，算完了！

但是如果我们简单地这样递归，会出现大量重复计算的内容，所以我们应该要把他们放在同一个结构体里进行计算，整体递归，也就是说，在解决一组测试点的时候同时计算三组的数值，在需要的时候直接调用即可。

代码注意点：

• 部分反复出现的表达式可先求值再使用，减少代码量与常数。
• 取模部分逆元，参考 OI-Wiki。
• 结构体调用次序与递归次序。

基本上注意一些细节，代码逻辑并没有困难的地方，也不难编写。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int P = 998244353;
int i2=499122177,i6=166374059;
struct num{
	num(){f=g=h=0;}
	int f, g, h;
};
num calc(int n,int a,int b,int c){
	int ac=a/c,bc=b/c,m=(a*n+b)/c,n1=n+1,n21=n*2+1;
	num 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;
		d.g=ac*n%P*n1%P*n21%P*i6%P+bc*n%P*n1%P*i2%P;
		d.h=ac*ac%P*n%P*n1%P*n21%P*i6%P+bc*bc%P*n1%P+ac*bc%P*n%P*n1%P;
		d.f%=P,d.g%=P,d.h%=P;
		num e=calc(n,a%c,b%c,c);
		d.h+=e.h+2*bc%P*e.f%P+2*ac%P*e.g%P;
		d.g+=e.g,d.f+=e.f;
		d.f%=P,d.g%=P,d.h%=P;
		return d;
	}num 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;
}int T,n,a,b,c;
signed main(){
	scanf("%lld", &T);
	while (T--){
		scanf("%lld%lld%lld%lld", &n, &a, &b, &c);
		num ans=calc(n,a,b,c);
		printf("%lld %lld %lld\n",ans.f,ans.h,ans.g);
	}return 0;
}