类欧几里得算法

前言

注：该文章不定期更新。

Tips: 建议阅读文章后自行推导，否则难以掌握。

介绍

类欧几里得算法是用 \(O(\log n)\) 的时间复杂度求解形似于 \(f(a,b,c,n)=\sum\limits_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor\) 的函数的值的一种算法。

由于其算法复杂度证明与扩展欧几里得算法类似，因此闻名于类欧几里得算法。

其主要思想就是划分不同边界推式子进行递归运算。

题单

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

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

求下列函数的值。

\[f(a,b,c,n)=\sum_{i=0}^n\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor \]

\[g(a,b,c,n)=\sum_{i=0}^n\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor^2 \]

\[h(a,b,c,n)=\sum_{i=0}^ni\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor \]

思路

\(\text{(I)}\) 当 \(a < c\) 且 \(b < c\) 时。

先化简 \(f(a,b,c,n)\)。

\[\begin{aligned}f(a,b,c,n)&=\sum_{i=0}^n\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\\&=\sum_{i=0}^n\sum_{j=1}^{\lfloor\frac{ai+b}{c}\rfloor}\bigg[j\le\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\bigg]\\&=\sum_{i=0}^n\sum_{j=1}^{\lfloor\frac{an+b}{c}\rfloor}\bigg[j\le\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\bigg]\\&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg[j+1\le\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\bigg]\\&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg[cj+c\le{ai+b}\bigg]\\&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg[cj+c-b\le{ai}\bigg]\\&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg[cj+c-b - 1<{ai}\bigg]\\&=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg[\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor<i\bigg]\\&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=0}^n\bigg[\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor<i\bigg]\\&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=\lfloor\frac{cj+c-b - 1}{a}\rfloor+1}^n1\\&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg(n-\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor\bigg)\\&=n\bigg\lfloor\frac{an+b}{c}\bigg\rfloor-\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\bigg\lfloor\frac{cj+c-b - 1}{a}\bigg\rfloor\\&=n\bigg\lfloor\frac{an+b}{c}\bigg\rfloor-f(c,c+b-1,a,\bigg\lfloor\frac{an+b}{c}\bigg\rfloor-1)\\\end{aligned}\]

令 \(m = \lfloor\frac{an+b}{c}\rfloor\)，则有：

\[f(a,b,c,n) = nm-f(c,c-b-1,a,m-1) \]

对于上述推导，我们称之为“引理1”：

引理1：

\[\sum_{i=0}^n\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=\lfloor\frac{cj+c-b - 1}{a}\rfloor+1}^n1 \]

接下来考虑 \(h(a,b,c,n)\) 的化简，根据“引理1”可得：

\[\begin{aligned}h(a,b,c,n)&=\sum_{i=0}^ni\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\\&=\sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=\lfloor\frac{cj+c-b - 1}{a}\rfloor+1}^ni\end{aligned}\]

记 \(t = \lfloor\frac{cj+c-b-1}{a}\rfloor, m = \lfloor\frac{an+b}{c}\rfloor\)，则有：

\[\begin{aligned}h(a,b,c,n)&= \sum_{j=0}^{\lfloor\frac{an+b}{c}\rfloor-1}\sum_{i=\lfloor\frac{cj+c-b - 1}{a}\rfloor+1}^ni\\&=\sum_{j=0}^{m-1}\sum_{i=t+1}^ni\\&=\sum_{j=0}^{m-1}\frac{(t+n+1)(n-t)}{2}\end{aligned}\]

此时我们得到“引理2”：

引理2：

令 \(t = \lfloor\frac{cj+c-b-1}{a}\rfloor, m = \lfloor\frac{an+b}{c}\rfloor\)，有：

\[\sum_{i=0}^ni\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor = \sum_{j=0}^{m-1}\frac{(t+n+1)(n-t)}{2} \]

由于 \(t\) 的表达式中的 \(j\) 与求和相关，所以我们把 \(t\) 单独提出来。

\[\begin{aligned}\frac{(t+n)(n-t+1)}{2}&=\frac{1}{2}(n^2-t^2-t+n)\\&=\frac{1}{2}((n^2+n)-(t^2+t))\end{aligned}\]

于是可以化简原式。

\[\begin{aligned}\sum_{j=0}^{m-1}\frac{(t+n+1)(n-t)}{2}&=\sum_{j=0}^{m-1}\frac{1}{2}\bigg((n^2+n)-(t^2+t)\bigg)\\&=\frac{1}{2}\sum_{j=0}^{m-1}\bigg(n^2+n\bigg)- \frac{1}{2}\sum_{j=0}^{m-1}\bigg(t^2+t\bigg)\\&=\frac{mn^2+mn}{2}-\frac{1}{2}\sum_{j=0}^{m-1}t^2-\frac{1}{2}\sum_{j=0}^{m-1}t\\&=\frac{1}{2}\bigg(mn^2+mn-\sum_{j=0}^{m-1}\bigg\lfloor\frac{cj+c-b-1}{a}\bigg\rfloor^2-\sum_{j=0}^{m-1}\bigg\lfloor\frac{cj+c-b-1}{a}\bigg\rfloor\bigg)\\&=\frac{1}{2}\bigg(mn(n+1)-g(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)\bigg)\end{aligned}\]

然后考虑 \(g(a,b,c,n)\) 的化简，我们有一次求和公式 \(\sum\limits_{i=1}^n i = \frac{n^2+n}{2}\)，可以反过来得到 \(2\sum\limits_{i=1}^n i - n = n^2\)，于是我们的 \(g(a,b,c,n)\) 可以变成：

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

根据“引理2”可知，令 \(t = \lfloor\frac{cj+c-b-1}{a}\rfloor, m = \lfloor\frac{an+b}{c}\rfloor\)，有：

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

由“引理1”可知：

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

由此，当 \(a \le c\) 且 \(b \le c\) 时，我们有：

\[\begin{aligned}&f(a,b,c,n) = nm-f(c,c-b-1,a,m-1)\\&g(a,b,c,n) = (m+1)mn-2\bigg(h(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)\bigg)-f(a,b,c,n)\\&h(a,b,c,n) = \frac{1}{2}\bigg(mn(m+1)-g(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)\bigg)\end{aligned}\]

\(\text{(II)}\) 当 \(a \ge c\) 或 \(b \ge c\) 时，我们将式子完全展开，令 \(a'=a \mod c\)，\(b'=b \mod c\)。

\[\begin{aligned}f(a,b,c,n) &= \sum_{i=0}^n\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\\&=\sum_{i=0}^n\bigg(\bigg\lfloor\frac{a'i+b'}{c}\bigg\rfloor+i\bigg\lfloor\frac{a}{c}\bigg\rfloor+\bigg\lfloor\frac{b}{c}\bigg\rfloor\bigg)\\&=f(a',b',c,n)+\frac{n(n+1)}{2}\bigg\lfloor\frac{a}{c}\bigg\rfloor+(n+1)\bigg\lfloor\frac{b}{c}\bigg\rfloor\\g(a,b,c,n) &= \sum_{i=0}^n\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor^2\\&=\sum_{i=0}^n\bigg(\bigg\lfloor\frac{a'i+b'}{c}\bigg\rfloor+i\bigg\lfloor\frac{a}{c}\bigg\rfloor+\bigg\lfloor\frac{b}{c}\bigg\rfloor\bigg)^2\\&=\sum_{i=0}^n\bigg(\bigg\lfloor\frac{a'i+b'}{c}\bigg\rfloor^2+i^2\bigg\lfloor\frac{a}{c}\bigg\rfloor^2+\bigg\lfloor\frac{b}{c}\bigg\rfloor^2+2i\bigg\lfloor\frac{a'i+b'}{c}\bigg\rfloor+2i\bigg\lfloor\frac{a}{c}\bigg\rfloor\bigg\lfloor\frac{b}{c}\bigg\rfloor+2\bigg\lfloor\frac{b}{c}\bigg\rfloor\bigg\lfloor\frac{a'i+b'}{c}\bigg\rfloor\bigg)\\&=g(a',b',c,n)+\frac{n(n+1)(2n+1)}{6}\bigg\lfloor\frac{a}{c}\bigg\rfloor^2+(n+1)\bigg\lfloor\frac{b}{c}\bigg\rfloor^2+2\bigg(h(a',b',c,n)+\bigg\lfloor\frac{b}{c}\bigg\rfloor f(a',b',c,n)+\frac{n(n+1)}{2}\bigg\lfloor\frac{a}{c}\bigg\rfloor\bigg\lfloor\frac{b}{c}\bigg\rfloor\bigg)\\h(a,b,c,n)&=\sum_{i=0}^ni\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\\&=\sum_{i=0}^ni\bigg(\bigg\lfloor\frac{a'i+b'}{c}\bigg\rfloor+i\bigg\lfloor\frac{a}{c}\bigg\rfloor+\bigg\lfloor\frac{b}{c}\bigg\rfloor\bigg)\\&=\sum_{i=0}^n h(a',b',c,n)+\frac{n(n+1)(2n+1)}{6}\bigg\lfloor\frac{a}{c}\bigg\rfloor+\frac{n(n+1)}{2}\bigg\lfloor\frac{b}{c}\bigg\rfloor\end{aligned}\]

根据公式写代码，为了防止已经算过的数据被重复计算，我们用结构体来存储三个函数同步计算，丑死了（小声）。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353, inv2 = 499122177, inv6 = 166374059;
int T;
ll a, b, c, n;
struct Node
{ll f, g, h;
};Node solve(ll a, ll b, ll c, ll n)
{Node ans, tmp;if (!a) return (Node){(b / c) * (n + 1) % mod, (b / c) * (b / c) % mod * (n + 1) % mod, (b / c) * n % mod * (n + 1) % mod * inv2 % mod};if (a < c && b < c){ll m = (a * n + b) / c;if (!m) return (Node){0, 0, 0};tmp = solve(c, c - b - 1, a, m - 1);m %= mod;ans.f = (m * n % mod - tmp.f + mod) % mod;ans.g = ((m * (m + 1) % mod * n % mod - 2 * tmp.h - 2 * tmp.f - ans.f) % mod + mod) % mod;ans.h = ((m * n % mod * (n + 1) % mod - tmp.f - tmp.g) % mod + mod) % mod * inv2 % mod;return ans;}tmp = solve(a % c, b % c, c, n);ans.f = (tmp.f + n * (n + 1) % mod * inv2 % mod * (a / c) % mod + (n + 1) * (b / c) % mod) % mod;ans.g = (tmp.g + (a / c) * (a / c) % mod * n % mod * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod + (n + 1) * (b / c) % mod * (b / c) % mod + 2 * (a / c) % mod * tmp.h % mod + 2 * (b / c) * tmp.f % mod + 2 * (a / c) * (b / c) % mod * n % mod * (n + 1) % mod * inv2 % mod) % mod;ans.h = (tmp.h + (a / c) * n % mod * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod + (b / c) * n % mod * (n + 1) % mod * inv2 % mod) % mod;return ans;
}void solve()
{scanf("%lld%lld%lld%lld", &n, &a, &b, &c);Node ans = solve(a, b, c, n);printf("%lld %lld %lld\n", ans.f, ans.g, ans.h);
}int main()
{scanf("%d", &T);while (T -- ) solve();return 0;
}

P5171 Earthquake

P5171 Earthquake

给定 \(a,\,b,\,c\) ，求满足方程 \(ax+by \leqslant c\) 的非负整数解个数。

思路

通过移项，我们可以得到：

\[x\leqslant\frac{c - by}{a},\,y\leqslant\frac{c - ax}{b} \]

由于 \(x,\,y\) 均为非负整数，我们可以令 \(x = y = 0\)，则 \(x \leqslant \lfloor\frac{c}{a}\rfloor,\,y \leqslant \lfloor\frac{c}{b}\rfloor\)可以得到原方程的意义就是下面这个式子。

\[\sum_{i=0}^{\lfloor\frac{c}{a}\rfloor}\sum_{j=0}^{\lfloor\frac{c}{b}\rfloor}\bigg[j\leqslant\bigg\lfloor\frac{c - ai}{b}\bigg\rfloor\bigg]=\sum_{i=0}^{\lfloor\frac{c}{a}\rfloor}\bigg(\bigg\lfloor\frac{c - ai}{b}\bigg\rfloor+1\bigg) \]

这个式子展开之后和我们刚才推的公式的形式很像，于是我们想办法展开。

\[\sum_{i=0}^{\lfloor\frac{c}{a}\rfloor}\bigg\lfloor\frac{c - ai}{b}\bigg\rfloor+\bigg\lfloor\frac{c}{a}\bigg\rfloor+1 \]

为了让我们的公式形式和上面完全一致，需要把“\(-\)”改为“\(+\)”，于是我们可以在内函数加上一个 \(i\)：

\[\sum_{i=0}^{\lfloor\frac{c}{a}\rfloor}\bigg\lfloor\frac{c - ai}{b}+i-i\bigg\rfloor+\bigg\lfloor\frac{c}{a}\bigg\rfloor+1=\sum_{i=0}^{\lfloor\frac{c}{a}\rfloor}\bigg\lfloor\frac{c+(b-a)i}{b}\bigg\rfloor-\frac{(\lfloor\frac{c}{a}\rfloor+1)\lfloor\frac{c}{a}\rfloor}{2}+\bigg\lfloor\frac{c}{a}\bigg\rfloor+1 \]

合并一下就是我们这题的公式：

\[\sum_{i=0}^{\lfloor\frac{c}{a}\rfloor}\bigg\lfloor\frac{c+(b-a)i}{b}\bigg\rfloor-\frac{(\lfloor\frac{c}{a}\rfloor-1)\lfloor\frac{c}{a}\rfloor}{2}+1 \]

为了保证满足 \(f(a,b,c,n) = \sum\limits_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor\) 所有参数为非负的形式，我们需要让 \(b-a\geqslant0\)，由于 \(a,\,b\) 等价，当 \(a>b\) 时直接 swap(a,b) 即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, c;ll solve(ll a, ll b, ll c, ll n)
{if (!a) return b / c * (n + 1);if (a < c && b < c){ll m = (a * n + b) / c;if (!m) return 0;return n * m - solve(c, c - b - 1, a, m - 1);}return solve(a % c, b % c, c, n) + (n + 1) * n / 2 * (a / c) + (n + 1) * (b / c);
}int main()
{cin >> a >> b >> c;if (a > b) swap(a, b);cout << solve(b - a, c, b, c / a) - (c / a) * (c / a - 1) / 2 + 1;return 0;
}

[ABC372G] Ax + By < C

[ABC372G] Ax + By < C(luogu)

G - Ax + By < C(Atcoder)

与 P5171 Earthquake 完全类似。

不过上题是给定 \(a,\,b,\,c\) ，求满足方程 \(ax+by \leqslant c\) 的非负整数解个数。

本题是给定 \(a,\,b,\,c\) ，求满足方程 \(ax+by<c\) 的正整数解个数。

思路

同样的移项后可以得到：

\[0<x<\frac{c - by}{a},\,0<y<\frac{c - ax}{b} \]

而 \(x,y\) 有限制为 \(0<x\leqslant\lfloor\frac{c-b-1}{a}\rfloor,\,0<y\leqslant\lfloor\frac{c-a-1}{b}\rfloor\)

\[\begin{aligned} &\sum_{i=1}^{\lfloor\frac{c-b-1}{a}\rfloor}\sum_{j=1}^{\lfloor\frac{c-a-1}{b}\rfloor}\bigg[j\leqslant\bigg\lfloor\frac{c-ai-1}{b}\bigg\rfloor\bigg] \\&=\sum_{i=1}^{\lfloor\frac{c-b-1}{a}\rfloor}\bigg\lfloor\frac{c-ai-1}{b}\bigg\rfloor\end{aligned} \]

为了使 \(i\) 前的系数大于零，我们不妨考虑整体 \(+i-i\)。

\[\begin{aligned}&\sum_{i=1}^{\lfloor\frac{c-b-1}{a}\rfloor}\bigg\lfloor\frac{c-ai-1}{b}+i-i\bigg\rfloor \\&=\sum_{i=1}^{\lfloor\frac{c-b-1}{a}\rfloor}\bigg\lfloor\frac{(b-a)i+c-1}{b}\bigg\rfloor-\sum_{i=1}^{\lfloor\frac{c-b-1}{a}\rfloor}i \\&=\sum_{i=1}^{\lfloor\frac{c-b-1}{a}\rfloor}\bigg\lfloor\frac{(b-a)i+c-1}{b}\bigg\rfloor-\frac{\lfloor\frac{c-b-1}{a}\rfloor(\lfloor\frac{c-b-1}{a}\rfloor+1)}{2}\end{aligned} \]

对于 \(\sum\limits_{i=1}^{\lfloor\frac{c-b-1}{a}\rfloor}\lfloor\frac{(b-a)i+c-1}{b}\rfloor\) 可以类欧快速求解 \(f(b-a,\,c-1,\,b,\,\lfloor\frac{c-b-1}{a}\rfloor)-f(b-a,\,c-1,\,b,\,0)\)，为了让 \(b - a\) 不为负，考虑 \(b - a < 0\) 时 swap(a, b) 即可。

以上是对于唯一 \(a,\,b,\,c\) 的单次求解，那么多元呢？

我们不妨考虑对于每条直线 \(A_ix+B_iy=C_i\) 本质上对空间进行了一次切割，我们想要找到的是所有直线在原点一侧的半平面交。

引用 ATCoder 上的一张图片，我们实际上想要找到的是左下角的点集，如果我们按照斜率排序，可以找到相邻两条直线的交点 \([x1,\,x2,\,...,\,x_k]\)，我们对于 \([x_j,\,x_{j+1})\) 必定属于一条直线 \(l\)，若 \(a,\,b,\,c\) 为直线 \(l\) 的三个参数，记 \(g(x) = \sum\limits_{i=1}^{x}\lfloor\frac{-ai+c-1}{b}\rfloor\)，那么对于 \([x_j, x_{j+1})\) 区间上直线 \(l\) 下正整数点的个数为 \(g(x_{j+1}-1) - g(x_j-1)\)。

这样我们的问题就转变为了找到这样 \(k\) 个点。

首先我们的点的横坐标有上下界 \([1,\min\{\lceil\frac{c_1}{a_1}\rceil,\,...,\,\lceil\frac{c_i}{a_i}\rceil,\,...,\,\lceil\frac{c_n}{a_n}\rceil\}]\)。

维护一个单调栈使得栈内点横坐标单调递增，如果存在两条相邻斜率的直线交点的横坐标较小，那必然可以把大的舍去，因为不需要进行计算了。

这样这个问题就变成了对于交点集 \([x1,\,x2,\,...,\,x_k]\)，求所有 \([x_j, x_{j+1})\) 区间上直线 \(l\) 下正整数点的个数 \(g(x_{j+1}-1) - g(x_j-1)\) 之和。

不过需要注意的是，我们的类欧的参数需要为正，此时的 \(a,\,b\) 就不等价了，这如何做到呢？

事实上有：

\[\begin{aligned}&\sum_{i=1}^{\lfloor\frac{c-b-1}{a}\rfloor}\bigg\lfloor\frac{c-ai-1}{b}\bigg\rfloor \\&=\sum_{i=1}^{\lfloor\frac{c-b-1}{a}\rfloor}\bigg\lfloor\frac{c-ai-1}{b}+ki-ki\bigg\rfloor \\&=\sum_{i=1}^{\lfloor\frac{c-b-1}{a}\rfloor}\bigg\lfloor\frac{(kb-a)i+c-1}{b}\bigg\rfloor-\frac{k\lfloor\frac{c-b-1}{a}\rfloor(\lfloor\frac{c-b-1}{a}\rfloor+1)}{2}\end{aligned} \]

这样的 \(k\) 是很好找的，只需要 \(k = \lceil\frac{a}{b}\rceil\) 即可。

参考代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
const ll INF = 1e18;
struct Node
{ll a, b, c;
}line[N];
ll x[N], q[N];
Node stk[N];bool cmp(Node x, Node y)
{if (x.a * y.b == y.a * x.b) return x.c * y.a < y.c * x.a;return x.a * y.b < y.a * x.b;
}ll calc(ll a, ll b, ll c, ll n)
{if (n < 0) return 0;if (!a) return b / c * (n + 1);if (a < c && b < c){ll m = (a * n + b) / c;if (!m) return 0;return n * m - calc(c, c - b - 1, a, m - 1);}return calc(a % c, b % c, c, n) + (n + 1) * n / 2 * (a / c) + (n + 1) * (b / c);
}ll get(Node line, ll l, ll r, ll xmin)
{l = min(xmin, max(1ll, l)) - 1, r = min(xmin, max(1ll, r)) - 1;ll a = line.a, b = line.b, c = line.c;ll k = (a + b - 1) / b;return calc(k * b - a, c - 1, b, r) - k * r * (r + 1) / 2 - calc(k * b - a, c - 1, b, l) + k * l * (l + 1) / 2;
}ll inter(Node l1, Node l2)
{return (l2.c * l1.b - l1.c * l2.b - 1) / (l1.b * l2.a - l2.b * l1.a) + 1;
}void solve()
{ll n, cntx = 0, cnt = 0, ans = 0, xmin = 1e18;cin >> n;for (int i = 1; i <= n; i ++ ) cin >> line[i].a >> line[i].b >> line[i].c;sort(line + 1, line + n + 1, cmp);for (int i = 1; i <= n; i ++ ){ll a = line[i].a, b = line[i].b, c = line[i].c;if (cnt && stk[cnt].a * b == stk[cnt].b * a) continue;while (cnt >= 2 && inter(stk[cnt], line[i]) <= x[cntx]) cnt -- , cntx -- ;xmin = min((c + a - 1) / a, xmin);stk[ ++ cnt] = line[i];if (!cntx) x[ ++ cntx] = -INF;else x[ ++ cntx] = inter(stk[cnt - 1], line[i]);}x[ ++ cntx] = INF;for (int i = 1; i <= cnt; i ++ ) ans += get(stk[i], x[i], x[i + 1], xmin);cout << ans << endl;
}int main()
{int T;cin >> T;while (T -- ) solve();return 0;
}

T387782 开根

U371108 开根

求下列式子的值。

\[\sum_{i=0}^ni\bigg\lfloor{i}\sqrt{\theta}+i\theta\bigg\rfloor \]

思路

如果令 \(\sqrt{\theta}=x\)，那么我们需要求出 \(\sum\limits_{i=0}^ni\lfloor{i}(x+\theta)\rfloor\) 的值，由于 \(i=0\) 时不影响函数的求和，我们求出 \(\sum\limits_{i=1}^ni\lfloor{i}(x+\theta)\rfloor\) 即可，考虑构造下列三个函数。

\[\begin{aligned}&f(a,b,c,n)=\sum_{i=1}^n\bigg\lfloor \frac{ax+b}{c}·i\bigg\rfloor\\&g(a,b,c,n)=\sum_{i=1}^ni\bigg\lfloor \frac{ax+b}{c}·i\bigg\rfloor\\&h(a,b,c,n)=\sum_{i=1}^n\bigg\lfloor \frac{ax+b}{c}·i\bigg\rfloor^2\end{aligned}\]

为了让函数进行递归，我们从最简单的函数开始考虑化简。

令 \(t = \frac{ax+b}{c}\)，当 \(t \geqslant 1\) 时。

\[\begin{aligned}f(a,b,c,n)&=\sum_{i=1}^n\bigg\lfloor \frac{ax+b}{c}·i\bigg\rfloor\\&=\sum_{i=1}^n\bigg\lfloor ti\bigg\rfloor\\&=\sum_{i=1}^n\bigg\lfloor ti-\lfloor t \rfloor i +\lfloor t \rfloor i\bigg\rfloor\\&=\sum_{i=1}^n\bigg\lfloor (t-\lfloor t \rfloor)i +\lfloor t \rfloor i\bigg\rfloor\\&=\sum_{i=1}^n\bigg\lfloor (t-\lfloor t \rfloor)i\bigg\rfloor+\frac{n(n+1)}{2}\lfloor t\rfloor\\&=\sum_{i=1}^n\bigg\lfloor\frac{ax+b-c\lfloor t\rfloor}{c}i\bigg\rfloor+\frac{n(n+1)}{2}\lfloor t\rfloor\\&=f(a,b-c\lfloor t\rfloor,c,n)+\frac{n(n+1)}{2}\lfloor t\rfloor\end{aligned}\]

类似的，我们可以得到：

\[g(a,b,c,n)=g(a,b-c\lfloor t\rfloor,c,n)+\frac{n(n+1)(2n+1)}{6}\lfloor t\rfloor \]

\[h(a,b,c,n)=h(a,b-c\lfloor t\rfloor,c,n)+\lfloor t\rfloor g(a,b-c\lfloor t\rfloor,c,n)+\frac{n(n+1)(2n+1)}{6}\lfloor t\rfloor^2 \]

其中 \(h\) 函数只需要把平方暴力拆开即可。

然后考虑 \(t < 1\) 时，令 \(t = \frac{ax+b}{c},\,m=\lfloor tn\rfloor\)。

\[\begin{aligned}f(a,b,c,n)&=\sum_{i=1}^n\bigg\lfloor ti\bigg\rfloor\\&=\sum_{i=1}^n\sum_{j=1}^{\lfloor ti\rfloor}\bigg[j<ti\bigg]\\&=\sum_{i=1}^n\sum_{j=1}^m\bigg[j<ti\bigg]\\&=\sum_{i=1}^n\sum_{j=1}^m\bigg[\frac{j}{t}<i\bigg]\\&=\sum_{i=1}^n\sum_{j=1}^m\bigg[\frac{cj}{ax+b}<i\bigg]\\&=\sum_{i=1}^m\sum_{j=1}^n\bigg[\bigg\lfloor\frac{cj}{ax+b}\bigg\rfloor<i\bigg]\\&=\sum_{j=1}^m\sum_{i=\lfloor\frac{cj}{ax+b}\rfloor+1}^n1\\&=\sum_{j=1}^m\bigg(n-\bigg\lfloor\frac{cj}{ax+b}\bigg\rfloor\bigg)\\&=nm-\sum_{j=1}^m\bigg\lfloor\frac{cj}{ax+b}\bigg\rfloor\\&=nm-\sum_{j=1}^m\bigg\lfloor\frac{cj(ax-b)}{a^2x^2-b^2}\bigg\rfloor\\&=nm-\sum_{j=1}^m\bigg\lfloor\frac{acx-bc}{a^2\theta-b^2}·j\bigg\rfloor\\&=nm-f(ac,-bc,a^2\theta-b^2,m)\end{aligned}\]

类似的，化简 \(g\) 和 \(h\)，根据 \(f\) 化简的结论，我们快速写出式子。

\[\begin{aligned}g(a,b,c,n)&=\sum_{i=1}^ni\bigg\lfloor \frac{ax+b}{c}·i\bigg\rfloor\\&=\sum_{i=1}^m\sum_{j=\lfloor\frac{cj}{ax+b}\rfloor+1}^ni\\\end{aligned}\]

设 \(m_j=\lfloor\frac{cj}{ax+b}\rfloor\)，由等差数列求和可得：

\[=\sum_{j=1}^m\frac{(n+m_j+1)(n-m_j)}{2} \]

相关项分离可得：

\[\begin{aligned}&=\frac{1}{2}\sum_{j=1}^m\bigg((n^2+n)-(m_j^2+m_j)\bigg)\\&=\frac{1}{2}\bigg(\sum_{j=1}^m(n^2+n)-\sum_{j=1}^m(m_j^2+m_j)\bigg)\\&=\frac{1}{2}\bigg(m(n^2+n)-\sum_{j=1}^mm_j^2-\sum_{j=1}^mm_j\bigg)\\&=\frac{1}{2}\bigg(m(n^2+n)-\sum_{j=1}^m\bigg\lfloor\frac{cj}{ax+b}\bigg\rfloor^2-\sum_{j=1}^m\bigg\lfloor\frac{cj}{ax+b}\bigg\rfloor\bigg)\\&=\frac{1}{2}\bigg(m(n^2+n)-h(ac,-bc,a^2\theta-b^2,m)-f(ac,-bc,a^2\theta-b^2,m)\bigg)\end{aligned}\]

化简 \(h\) 时我们需要知道 \(n^2 = 2\sum\limits_{i=1}^ni-n\)，这样便能愉快地化简了。

\[\begin{aligned}h(a,b,c,n)&=\sum_{i=1}^n\bigg\lfloor ti\bigg\rfloor^2\\&=\sum_{i=1}^n\bigg(\sum_{j=1}^{\lfloor ti\rfloor}j-\bigg\lfloor ti\bigg\rfloor\bigg)\\&=\sum_{i=1}^n\sum_{j=1}^{\lfloor ti\rfloor}j-\sum_{i=1}^n\bigg\lfloor ti\bigg\rfloor\\&=\sum_{i=1}^n\sum_{j=1}^{\lfloor tn\rfloor}\bigg[j<ti\bigg]j-\sum_{i=1}^n\bigg\lfloor ti\bigg\rfloor\\&=\sum_{j=1}^m\sum_{i=\lfloor\frac{cj}{ax+b}\rfloor+1}^nj-\sum_{i=1}^n\bigg\lfloor ti\bigg\rfloor\\&=\sum_{j=1}^m\bigg(n-\bigg\lfloor\frac{cj}{ax+b}\bigg\rfloor\bigg)j-\sum_{i=1}^n\bigg\lfloor ti\bigg\rfloor\\&=\frac{m(m+1)}{2}n-\sum_{j=1}^m\bigg\lfloor\frac{cj}{ax+b}\bigg\rfloor j-\sum_{i=1}^n\bigg\lfloor ti\bigg\rfloor\\&=\frac{1}{2}\bigg(nm(m+1)-2g(ac,-bc,a^2\theta,m)-2f(a,b,c,n)\bigg)\end{aligned}\]

我们的答案即是 \(g(1,\theta,1,n)\)。

递归过程中可能出现许多被重复计算的值，所以我们用结构体存储 \(f,\,g,\,h\)，同样，为了防止求解 \(t\) 时分子分母过大，我们每次运算前都除以其最大公约数。

时间复杂度 \(O(T\log{n})\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll mod = 998244353, inv2 = 499122177, inv6 = 166374059;
ll T, n, theta;
ld x;
struct Node
{ll f, g, h;
};Node solve(ll a, ll b, ll c, ll n)
{if (!n) return Node{0, 0, 0};ll d = __gcd(a, __gcd(b, c));a /= d, b /= d, c /= d;Node tmp, ans;ll t = (a * x + b) / c;if (!t){ll m = (a * x + b) / c * n;tmp = solve(a * c, -b * c, a * a * theta - b * b, m);ans.f = ((n * m - tmp.f) % mod + mod) % mod;ans.g = ((n * (n + 1) % mod * m % mod - tmp.f - tmp.h) % mod + mod) % mod * inv2 % mod;ans.h = ((m * (m + 1) % mod * n % mod - 2 * tmp.g - 2 * ans.f) % mod + mod) % mod * inv2 % mod;return ans;}tmp = solve(a, b - c * t, c, n);ans.f = (n * (n + 1) % mod * t % mod * inv2 + tmp.f) % mod;ans.g = (n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod * t % mod + tmp.g) % mod;ans.h = (n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod * t % mod * t % mod + t * tmp.g % mod + tmp.h) % mod;return ans;
}int main()
{scanf("%lld", &T);while (T -- ){scanf("%lld%lld", &n, &theta);x = sqrt(theta);ll s = x;if (!n || !theta) puts("0");else if (n == 1) printf("%lld\n", s + theta);else if (s * s == theta) printf("%lld\n", (n * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod * s % mod + n * (n + 1) % mod * inv2 % mod * theta % mod) % mod);else printf("%lld\n", solve(1, theta, 1, n).g);}return 0;
}

[2014清华集训] Sum

[2014清华集训] Sum(UOJ)

P5172 Sum(Luogu)

给定正整数 \(n,\,r\) ，求：

\[\sum_{d=1}^{n}(-1)^{\lfloor d\sqrt{r} \rfloor} \]

思路

首先这个式子看起来就不是很好递归的样子，我们把 \(-1\) 单独拿出来讨论，其 \(n\) 次幂必定满足：

\[(-1)^n = \begin{cases}1 & ,n \bmod 2=0 \\-1 & ,n \bmod 2=1 \end{cases}\]

我们把这个东西放进我们的式子。

\[\begin{aligned}(-1)^n&=1-2\bigg(n \bmod 2\bigg)\\&=1-2\bigg(n - 2\bigg\lfloor\frac{n}{2}\bigg\rfloor\bigg)\\&=1-2n+4\bigg\lfloor\frac{n}{2}\bigg\rfloor\end{aligned}\]

再回到原式，我们就可以发现：

\[\sum_{d=1}^{n}(-1)^{\lfloor d\sqrt{r} \rfloor}=\sum_{d=1}^{n}\bigg(1-2\bigg\lfloor d\sqrt{r} \bigg\rfloor+4\bigg\lfloor\frac{d\sqrt{r}}{2}\bigg\rfloor\bigg) \]

发现了什么？这不是和我们刚刚推得式子一模一样吗？

展开后得到：

\[n-2\sum_{d=1}^{n}\bigg\lfloor d\sqrt{r} \bigg\rfloor+4\sum_{d=1}^{n}\bigg\lfloor\frac{d\sqrt{r}}{2}\bigg\rfloor \]

刚刚我们推得式子是：

\[f(a,b,c,n)=\sum_{i=1}^n\bigg\lfloor \frac{ax+b}{c}·i\bigg\rfloor \]

当 \(x=\sqrt{r}\) 时，分别令 \(a=1,\,b=0,\,c=1\) 和 \(a=1,\,b=0,\,c=2\)，那么答案就显而易见了。

\[n-2f(1,0,1,n)+4f(1,0,2,n) \]

飞速的改一下版子（雾）。

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
double x;
ll T, n, r;ll solve(ll a, ll b, ll c, ll n)
{if (!n) return 0;ll d = __gcd(a, __gcd(b, c));a /= d, b /= d, c /= d;ll t = (a * x + b) / c;if (!t){ll m = (a * x + b) * n / c;return n * m - solve(a * c, -b * c, a * a * r - b * b, m);}return n * (n + 1) / 2 * t + solve(a, b - c * t, c, n);
}int main()
{cin >> T;while (T -- ){cin >> n >> r;x = sqrt(r);ll t = x;if (t * t == r) cout << ((t & 1) ? -(n & 1) : n) << endl;else cout << n - 2 * solve(1, 0, 1, n) + 4 * solve(1, 0, 2, n) << endl;}return 0;
}

[ABC283Ex] Popcount Sum

[ABC283Ex] Popcount Sum

记 \(\text{popcount}(n)\) 为 \(n\) 的二进制表示中 \(1\) 的个数。

现在有 \(T\) 组询问，每组询问给定 \(n, m, r\)，请求出

\[\sum_{i\bmod m = r}^n \text{popcount}(i) \]

思路

遇到这种同余类问题显然可以换为关于 \(k\) 的一元线性函数，也就是说我们可以用类欧去解决这种问题，为了更好地拟合我们上面的式子，我们把 \(i\) 换成 \(k\)，即 \(k \mod m = r\)，简单划一下式子。

\[im + r = k \le n \]

原式可化为：

\[\sum_{i=0}^{\lfloor\frac{n-r}{m}\rfloor} \text{popcount}(im+r) \]

拆位，每一位上是否含 \(1\) 我们可以这么表示。

设 \(P\) 为一正整数，\(P\) 的二进制位第 \(i\) 位上的数字应该为：

\[\bigg\lfloor\frac{P}{2^{i-1}}\bigg\rfloor - 2\bigg\lfloor\frac{P}{2^{i}}\bigg\rfloor \]

那么实际上就是这个东西。

\[\text{popcount}(im+r) = \sum_{j=1}^{\lfloor\log_2(im+r)\rfloor+1}\bigg(\bigg\lfloor\frac{im+r}{2^{j-1}}\bigg\rfloor - 2\bigg\lfloor\frac{im+r}{2^j}\bigg\rfloor\bigg) \]

从 \(j = 0\) 开始就是这么一个式子。

\[\sum_{j=0}^{\lfloor\log_2(im+r)\rfloor}\bigg(\bigg\lfloor\frac{im+r}{2^{j}}\bigg\rfloor - 2\bigg\lfloor\frac{im+r}{2^{j+1}}\bigg\rfloor\bigg) \]

很好，带回原式可以得到：

\[\sum_{i=0}^{\lfloor\frac{n-r}{m}\rfloor}\sum_{j=0}^{\lfloor\log_2(im+r)\rfloor}\bigg(\bigg\lfloor\frac{im+r}{2^{j}}\bigg\rfloor - 2\bigg\lfloor\frac{im+r}{2^{j+1}}\bigg\rfloor\bigg) \]

由于数的二进制位是有限的，且不存在的位数一定都是 \(0\)，所以我们可以把 \(\log_2{(im+r)}\) 改写为值域最高位，也就是 \(\log_2{n}\)，交换求和顺序，就是枚举每个 \(j\)，对 \(i\) 的函数进行类欧。

\[f(a,b,c,n)=\sum_{i=0}^n\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor \]

考虑发现也就是说求这个东西：

\[\sum_{j=0}^{\lfloor\log_2{n}\rfloor}\bigg(f(m,r,2^j,\bigg\lfloor\frac{n-r}{m}\bigg\rfloor)-2f(m,r,2^{j+1},\bigg\lfloor\frac{n-r}{m}\bigg\rfloor)\bigg) \]

上板子！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll calc(ll a, ll b, ll c, ll n)
{if (!a) return b / c * (n + 1);if (a < c && b < c){ll m = (a * n + b) / c;if (!m) return 0;return n * m - calc(c, c - b - 1, a, m - 1);}return calc(a % c, b % c, c, n) + (n + 1) * n / 2 * (a / c) + (n + 1) * (b / c);
}void solve()
{ll n, m, r, ans = 0;scanf("%lld%lld%lld", &n, &m, &r);int t = __lg(n);for (int i = 0; i <= t; i ++ ) ans += calc(m, r, 1 << i, (n - r) / m) - 2 * calc(m, r, 1 << i + 1, (n - r) / m);printf("%lld\n", ans);
}int main()
{int T;scanf("%d", &T);while (T -- ) solve();return 0;
}

[COCI2009-2010#1] ALADIN

P4433 [COCI2009-2010#1] ALADIN

给你 \(n(1 \le n \le 10^9)\) 个盒子，有 \(q(1 \le q \le 5 \times 10^4)\) 个操作，操作有两种：

• 第一种操作输入格式为 1 L R A B，表示将编号为 \(L\) 到 \(R\) 的盒子里的石头数量变为 \((X-L+1) \times A \bmod B\)，其中 \(X\) 为盒子的编号。
• 第二种操作输入格式为 2 L R，表示查询编号为 \(L\) 到 \(R\) 的盒子里的石头总数。

吐槽

一个极其恶心的类欧题，容易因为数据结构不熟练导致题目出错却找不到原因。

建立线段树变量多了还 MLE，浪费了我 2 天时间写一个题。

思路

首先注意到区间范围在 \(10^9\) 如此庞大的数量级上，我们知道，只能通过离散化之后再建立线段树才不会超出空间。

然后我们看向式子，是一个带模数的区间赋值，由 \(a \bmod b = a - b\lfloor\frac{a}{b}\rfloor\) 这个性质，我们考虑下面这个式子。

\[\sum_{i=0}^{n-1}(ai+b) \bmod c=\sum_{i=0}^{n-1}\bigg(ai+b-c\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor\bigg) \]

展开可以得到：

\[\frac{an(n-1)}{2}+bn-c\sum_{i=0}^{n-1}\bigg\lfloor\frac{ai+b}{c}\bigg\rfloor \]

对于这个式子最复杂的成分 \(\sum\limits_{i=0}^{n-1}\lfloor\frac{ai+b}{c}\rfloor\) 也就是一阶类欧的求和 \(f(a,\, b,\, c,\, n-1)\)。

对于区间赋值 \([L, R]\)，树上节点为 \([l, r]\)，若满足 \(L \le l \le r \le R\)，则该区间赋值有：

\[\sum_{i = l}^{r}(i-L+1) \times A \bmod B \]

改一下形式也就是：

\[\sum_{i = 0}^{r - l}\bigg(Ai+(l-L+1) \times A \bigg)\bmod B \]

此式子满足上述推导过程得到的结论，令 \(a = A,\, b = (l - L + 1) \times A,\, c = B,\, n = r - l + 1\)，可以发现，对于一个子段的赋值也就是 \(S(a,\,b,\,c,\,n-1) = \frac{an(n-1)}{2}+bn-cf(a,\,b,\,c,\,n-1)\)。

接下来考虑懒标记下传，为了维护式子的统一性，我们在每个节点内存储左端点 \(l\)，右端点 \(r\)，以及 \(a,\,b,\,c\) 的值，我们用大写字母来表示父亲的数据，\(T\) 表示父亲，\(tl,\, tr\) 分别表示左右儿子。

考虑 \(S(a,\,b,\,c,\,n-1)\) 的形式，由于 \(L\) 的不变性，\(a,\,b,\,c\) 显然为定值，唯一改变的就是 \(n - 1\) 的部分，而对于每个 \(n - 1\) 唯一对应线段树上一个节点所表示的区间范围 \([l,\, r]\)，因此左儿子的转移一定。

\[T(A,\,B,\,C) \to tl(a,\,b,\,c) \]

\[sum = S_{tl}(a,\,b,\,c,\, r_{tl} - l_{tl} + 1) \]

考虑右儿子同样发现只有 \(l\) 发生了改变，我们直接的将求和式中的 \(i\) 的下限从 \(0\) 改为 \(r_{tl}-l_{tl}+1\) 其实也就是 \(l_{tr}-L\)，简单推一下式子。

对于父亲有：

\[\sum_{i = 0}^{R - L}(Ai+B) \bmod C \]

对于右儿子有：

\[\sum_{i = l_{tr}-L}^{R - L}(ai+b) \bmod c \]

\[=\sum_{i = 0}^{R - L - l_{tr} + L}(A(i+l_{tr}-L)+B) \bmod C \]

\[=\sum_{i = 0}^{r_{tr} - l_{tr}}(Ai+(l_{tr}-L)A+B) \bmod C \]

可以发现 \(a = A,\, b = (l_{tr} - L)A + B,\, c = C,\, n = r_{tr} - l_{tl} + 1\)，对于常数 \(b\) 我们可以直接对 \(c\) 取个模防止暴毙。

代码如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 10;
int n, m, q[N][5], root, idx;
vector<int> v;
struct Node
{int l, r, ls, rs, a, b, c;ll sum;
}tr[N << 2];ll calc(ll a, ll b, ll c, ll n)
{if (!a) return b / c * (n + 1);if (a < c && b < c){ll m = (a * n + b) / c;if (!m) return 0;return n * m - calc(c, c - b - 1, a, m - 1);}return calc(a % c, b % c, c, n) + (n + 1) * n / 2 * (a / c) + (n + 1) * (b / c);
}ll solve(ll a, ll b, ll c, ll n)
{return n * (n - 1) / 2 * a - c * calc(a, b, c, n - 1) + b * n;
}void pushup(int p)
{tr[p].sum = tr[tr[p].ls].sum + tr[tr[p].rs].sum;
}void pushdown(int p)
{if (tr[p].c){tr[tr[p].ls].a = tr[p].a, tr[tr[p].ls].b = tr[p].b, tr[tr[p].ls].c = tr[p].c;tr[tr[p].rs].a = tr[p].a, tr[tr[p].rs].b = (1ll * tr[p].a * (tr[tr[p].rs].l - tr[p].l) + tr[p].b) % tr[p].c, tr[tr[p].rs].c = tr[p].c;tr[tr[p].ls].sum = solve(tr[tr[p].ls].a, tr[tr[p].ls].b, tr[tr[p].ls].c, tr[tr[p].ls].r - tr[tr[p].ls].l + 1);tr[tr[p].rs].sum = solve(tr[tr[p].rs].a, tr[tr[p].rs].b, tr[tr[p].rs].c, tr[tr[p].rs].r - tr[tr[p].rs].l + 1);tr[p].c = 0;}
}int build(int l, int r)
{int p = ++ idx;if (l == r){tr[p].l = v[l];tr[p].r = v[l + 1] - 1;return p;}int mid = l + r >> 1;tr[p].ls = build(l, mid), tr[p].rs = build(mid + 1, r);tr[p].l = tr[tr[p].ls].l, tr[p].r = tr[tr[p].rs].r;return p;
}void modify(int p, int l, int r, int a, int c)
{if (tr[p].l > r || tr[p].r < l) return;if (tr[p].l >= l && tr[p].r <= r){tr[p].a = a;tr[p].b = (tr[p].l - l + 1ll) * a % c;tr[p].c = c;tr[p].sum = solve(tr[p].a, tr[p].b, tr[p].c, tr[p].r - tr[p].l + 1);return;}pushdown(p);modify(tr[p].ls, l, r, a, c), modify(tr[p].rs, l, r, a, c);pushup(p);
}ll query(int p, int l, int r)
{if (tr[p].l > r || tr[p].r < l) return 0;if (tr[p].l >= l && tr[p].r <= r) return tr[p].sum;pushdown(p);return query(tr[p].ls, l, r) + query(tr[p].rs, l, r);
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= m; i ++ ){int op, l, r;scanf("%d%d%d", &op, &l, &r);q[i][0] = op, q[i][1] = l, q[i][2] = r;v.push_back(l), v.push_back(r + 1);if (op == 1){int a, b;scanf("%d%d", &a, &b);q[i][3] = a, q[i][4] = b;}}sort(v.begin(), v.end());v.erase(unique(v.begin(), v.end()), v.end());root = build(0, v.size() - 2);for (int i = 1; i <= m; i ++ )if (q[i][0] == 1) modify(root, q[i][1], q[i][2], q[i][3], q[i][4]);else printf("%lld\n", query(root, q[i][1], q[i][2]));return 0;
}