「bsoj4936」「模板题」类欧几里得 - 类欧几里得 附简要学习笔记

题目大意

    求：

$$g(a,b,c,l,r)=\sum_{i=l}^ri\lfloor\frac{ai+b}c\rfloor$$

---

前置技能

1. $$a\le\lfloor\frac cb\rfloor\Leftrightarrow ab\le c$$ 这个式子显然成立。
2. $$a\lt\lfloor\frac cb\rfloor\Leftrightarrow ab<c-b+1$$ 证明： $$\begin{aligned} a\lt\lfloor\frac cb\rfloor&\Leftrightarrow a\le\lfloor\frac cb\rfloor-1 \\ &\Leftrightarrow ab\le c-b \\ &\Leftrightarrow ab\lt c-b+1 \end{aligned}$$
3. $$n^2=2\cdot\frac{n(n+1)}{2}-n=2\sum_{i=0}^ni-n=2\sum_{i=1}^ni-n$$

---

类欧几里得算法

这是一道类欧几里得的模板题，类欧几里得模板有三种形式：

$$f(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}c\rfloor$$ $$g(a,b,c,n)=\sum_{i=0}^ni\lfloor\frac{ai+b}c\rfloor$$ $$h(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}c\rfloor^2$$

下文为了方便，记$m=\lfloor\frac{ai+b}c\rfloor$。

推$f$式

先来看最简单的$f$推导。

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

• 若$a\ge c$或$b\ge c$ $$\begin{aligned} f(a,b,c,n)&=\lfloor\frac ac\rfloor\frac {n(n+1)}2+\lfloor\frac bc\rfloor(n+1)+\sum_{i=0}^n\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor \\ &=\lfloor\frac ac\rfloor\frac {n(n+1)}2+\lfloor\frac bc\rfloor(n+1)+f(a\bmod c,b\bmod c,c,n) \end{aligned}$$
• $a,b\lt c$ $$\begin{aligned} f(a,b,c,n)&=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor \\ &=\sum_{i=0}^n\sum_{j=0}^{\lfloor\frac {ai+b}c\rfloor-1}1 \\ &=\sum_{j=0}^{m-1}\sum_{i=0}^n[j\lt\lfloor\frac {ai+b}c\rfloor] \\ &=\sum_{j=0}^{m-1}\sum_{i=0}^n[cj\lt(ai+b)-c+1] \\ &=\sum_{j=0}^{m-1}\sum_{i=0}^n[\lfloor\frac{cj+c-b-1}a\rfloor\lt i] \\ &=\sum_{j=0}^{m-1}(n-\lfloor\frac{cj+c-b-1}a\rfloor) \\ &=nm-\sum_{j=0}^{m-1}\lfloor\frac{cj+c-b-1}a\rfloor \\ &=nm-f(c,c-b-1,a,m-1) \end{aligned}$$ 然后递归处理即可。

推$g$式

$$g(a,b,c,n)=\sum_{i=0}^ni\lfloor\frac{ai+b}c\rfloor$$

• 若$a\ge c$或$b\ge c$ $$\begin{aligned} g(a,b,c,n)&=\lfloor\frac ac\rfloor\frac{n(n+1)(2n+1)}6+\lfloor\frac bc\rfloor\frac{n(n+1)}2+\sum_{i=0}^ni\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor \\ &=\lfloor\frac ac\rfloor\frac{n(n+1)(2n+1)}6+\lfloor\frac bc\rfloor\frac{n(n+1)}2+g(a\bmod c,b\bmod c,c,n) \end{aligned}$$
• 若$a,b\lt c$ $$\begin{aligned} g(a,b,c,n)&=\sum_{i=0}^ni\lfloor\frac{ai+b}c\rfloor \\ &=\sum_{i=0}^ni\sum_{j=0}^{\lfloor\frac{ai+b}c\rfloor-1}1 \\ &=\sum_{j=0}^{m-1}\sum_{i=0}^n[j\lt\lfloor\frac{ai+b}c\rfloor]i \\ &=\sum_{j=0}^{m-1}\sum_{i=0}^n[cj\lt(ai+b)-c+1]i \\ &=\sum_{j=0}^{m-1}\sum_{i=0}^n[\lfloor\frac{cj+c-b-1}a\rfloor\lt i]i \\ &=\sum_{j=0}^{m-1}\frac{(n-\lfloor\frac{cj+c-b-1}a\rfloor)(n+\lfloor\frac{cj+c-b-1}a\rfloor+1)}2 \\ &=\frac12\sum_{j=0}^{m-1}(n(n+1)-\lfloor\frac{cj+c-b-1}a\rfloor-\lfloor\frac{cj+c-b-1}a\rfloor^2) \\ &=\frac m2n(n+1)-\frac12\sum_{j=0}^{m-1}(\lfloor\frac{cj+c-b-1}a\rfloor+\lfloor\frac{cj+c-b-1}a\rfloor^2) \\ &=\frac m2n(n+1)-\frac12(f(c,c+b-1,a,m-1)+h(c,c+b-1,a,m-1)) \end{aligned}$$ 发现这个$g$很麻烦，递归时需要用到$f$和$h$，因此不妨先看看$h$的推导。

推$h$式

$$h(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}c\rfloor^2$$

• 若$a\ge c$或$b\ge c$ $$\begin{aligned} h(a,b,c,n)=&\sum_{i=0}^n(\lfloor\frac ac\rfloor i+\lfloor\frac bc\rfloor)^2+\sum_{i=0}^n2(\lfloor\frac ac\rfloor i+\lfloor\frac bc\rfloor)\lfloor\frac{(a\bmod c)i+(b\bmod c)}c\rfloor+\sum_{i=0}^n\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor^2 \\ =&\lfloor\frac ac\rfloor^2\frac{n(n+1)(2n+1)}6+\lfloor\frac bc\rfloor^2(n+1)+2\lfloor\frac ac\rfloor\lfloor\frac bc\rfloor\frac{n(n+1)}2 \\ &+2\sum_{i=0}^n\lfloor\frac ac\rfloor i\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor+2\sum_{i=0}^n\lfloor\frac bc\rfloor\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor+\sum_{i=0}^n\lfloor\frac{(a\bmod c)i+(b\bmod c)}{c}\rfloor^2 \\ =&\lfloor\frac ac\rfloor^2\frac{n(n+1)(2n+1)}6+\lfloor\frac bc\rfloor^2(n+1)+\lfloor\frac ac\rfloor\lfloor\frac bc\rfloor n(n+1) \\ &+2\lfloor\frac ac\rfloor g(a\bmod c,b\bmod c,c,n)+2\lfloor\frac bc\rfloor f(a\bmod c,b\bmod c,c,n)+h(a\bmod c,b\bmod c,c,n) \end{aligned}$$
• 若$a,b\lt c$
  此时我们需要用到前置技能中将平方展开成求和式的技巧。
  本人采用下标从$1$开始的展开式，当然也可以使用下标从$0$开始的展开式，但与之前的递推式下标不对应，等会儿讲计算方法的时候就不好处理。 $$\begin{aligned} h(a,b,c,n)&=\sum_{i=0}^n\lfloor\frac{ai+b}c\rfloor^2 \\ &=\sum_{i=0}^n(2\sum_{j=1}^{\lfloor\frac{ai+b}c\rfloor}j-\lfloor\frac{ai+b}c\rfloor) \\ &=2\sum_{j=0}^{m-1}(j+1)\sum_{i=0}^n[j\lt\lfloor\frac{ai+b}c\rfloor]-f(a,b,c,n) \\ &=2\sum_{j=0}^{m-1}(j+1)\sum_{i=0}^n[cj\lt(ai+b)-c+1]-f(a,b,c,n) \\ &=2\sum_{j=0}^{m-1}(j+1)\sum_{i=0}^n[\lfloor\frac{cj+c-b-1}a\rfloor\lt i]-f(a,b,c,n) \\ &=2\sum_{j=0}^{m-1}(j+1)(n-\lfloor\frac{cj+c-b-1}a\rfloor)-f(a,b,c,n) \\ &=2\sum_{j=0}^{m-1}(j+1)n-2\sum_{j=0}^{m-1}(j+1)\lfloor\frac{cj+c-b-1}a\rfloor-f(a,b,c,n) \\ &=2n\frac{m(m+1)}2-2\sum_{j=0}^{m-1}j\lfloor\frac{cj+c-b-1}a\rfloor-2\sum_{j=0}^{m-1}\lfloor\frac{cj+c-b-1}a\rfloor-f(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) \end{aligned}$$

计算方法

1. 按照递归式写出三个函数计算$f,g,h$并互相调用递归。
   直观可行，但会有很多状态被重复计算，时间效率低下。
2. 逐层递推
   发现每一个$f/g/h(a,b,c,n)$仅与$f/g/h(c,c-b-1,a,m-1)$有关（$h(a,b,c,n)$除外），因此我们不妨直接计算$f/g/h(c,c-b-1,a,m-1)$，然后计算出$f/g/h(a,b,c,n)$。
   这样可以有效减少重复状态，时间效率优良。

---

时间复杂度分析

原式的值仅与$a,b,c$有关，与$n$关系不大。
若采用逐层递推的方法：
仅观察函数的第一/三维，即可发现每次从二元组$(a,c)$变为$(c,a\bmod c)$，因此与欧几里得算法类似，时间复杂度近似与欧几里得算法相同。

---

总结

类欧几里得算法的思想是将一个多项式转为求和式。
利用$\sum$的交换与除法的蜜汁性质对原式进行变形。
当原式变形到$\sum$与限制条件兼容时，即可去掉$\sum$直接计数。
目标是得到一个范围更小的递归式。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const LL mod=1e9+7,inv2=500000004,inv6=166666668;

LL C2(LL n) {
	return (n*(n+1)>>1)%mod;
}

LL C6(LL n) {
	return n*(n+1)%mod*(2*n+1)%mod*inv6%mod;
}

void add(LL &x,LL v) {
	if(v>=mod)v%=mod;
	x+=v;
	if(x>=mod)x-=mod;
}

struct Data {
	LL f,g,h;
	Data(LL _f=0,LL _g=0,LL _h=0):f(_f),g(_g),h(_h) {}
};

Data Euclidean(LL a,LL b,LL c,LL n) {
	if(!a&&b<c)return Data();
	if(a>=c||b>=c) {
		Data now=Euclidean(a%c,b%c,c,n);
		n%=mod;
		LL _a=a/c,_b=b/c;
		add(now.h,_a*_a%mod*C6(n)%mod+_b*_b%mod*(n+1)%mod+_a*_b%mod*n%mod*(n+1)%mod+2*_a*now.g%mod+2*_b*now.f%mod);
		add(now.f,_a*C2(n)%mod+_b*(n+1)%mod);
		add(now.g,_a*C6(n)%mod+_b*C2(n)%mod);
		return now;
	}
	LL m=(a*n+b)/c;
	Data now,next=Euclidean(c,c-b-1,a,m-1);
	n%=mod,m%=mod;
	now.f=((n*m%mod-next.f)%mod+mod)%mod;
	now.g=((n*(n+1)%mod*m%mod-next.f-next.h)%mod+mod)%mod*inv2%mod;
	now.h=((n*m%mod*(m+1)%mod-2*next.g-2*next.f-now.f)%mod+mod)%mod;
	return now;
}

LL a,b,c,l,r;

int main() {
	a=Get_Int();
	c=Get_Int();
	b=Get_Int();
	l=Get_Int();
	r=Get_Int();
	printf("%lld\n",(Euclidean(a,b,c,r).g-Euclidean(a,b,c,l-1).g+mod)%mod);
	return 0;
}