【学习笔记】类欧几里得算法

userId_undefined
Lost
尊贵铂金传道者USACOGESP8级CSP-J一等奖CSP-S一等奖

2026-03-21 12:15:32

发布于：山东

13阅读
0回复
0点赞

没写完，以后还会更（）

引入

给定 a,b,c,na,b,c,n，计算下面表达式的值：

(∑i=0n⌊ai+bc⌋) mod 998244353(\sum\limits_{i=0}^n\lfloor\frac{ai+b}c\rfloor)\bmod 998244353

类欧几里得算法

考虑下面的恒等式：

⌊ai+bc⌋=⌊(⌊ac⌋c+a mod c)i+(⌊bc⌋c+b mod c)c⌋\lfloor\frac{ai+b}c\rfloor=\lfloor \frac{(\lfloor\frac ac\rfloor c+a\bmod c)i+(\lfloor\frac bc\rfloor c+b\bmod c)}c\rfloor

于是我们有：

∑i=0n⌊ai+bc⌋=∑i=0n⌊(⌊ac⌋c+a mod c)i+(⌊bc⌋c+b mod c)c⌋=∑i=0n⌊(a mod c)i+b mod cc⌋+∑i=0ni⌊ac⌋+∑i=0n⌊bc⌋=∑i=0n⌊(a mod c)i+b mod cc⌋+n(n+1)⌊ac⌋2+(n+1)⌊bc⌋\begin{aligned} &\sum\limits_{i=0}^n\lfloor\frac{ai+b}c\rfloor\\ =&\sum\limits_{i=0}^n\lfloor \frac{(\lfloor\frac ac\rfloor c+a\bmod c)i+(\lfloor\frac bc\rfloor c+b\bmod c)}c\rfloor\\ =&\sum\limits_{i=0}^n\lfloor\frac{(a\bmod c)i+b\bmod c}c\rfloor+\sum\limits_{i=0}^ni\lfloor\frac ac\rfloor+\sum\limits_{i=0}^n\lfloor\frac bc\rfloor\\ =&\sum\limits_{i=0}^n\lfloor\frac{(a\bmod c)i+b\bmod c}c\rfloor+\frac{n(n+1)\lfloor\frac ac\rfloor}2+(n+1)\lfloor\frac bc\rfloor\\ \end{aligned}

记 f(a,b,c,n)=∑i=0n⌊ai+bc⌋f(a,b,c,n)=\sum\limits_{i=0}^n\lfloor\frac{ai+b}c\rfloor，则有：

f(a,b,c,n)=f(a mod c,b mod c,c,n)+n(n+1)⌊ac⌋2+(n+1)⌊bc⌋f(a,b,c,n)=f(a\bmod c,b\bmod c,c,n)+\frac{n(n+1)\lfloor\frac ac\rfloor}2+(n+1)\lfloor\frac bc\rfloor

于是问题被转化为了 a,b<ca,b<c 的情况。此时考虑再做一个转化：

∑i=0n⌊ai+bc⌋=∑i=0n∑j=0⌊an+bc⌋−1[j<⌊ai+bc⌋]\begin{aligned} &\sum\limits_{i=0}^n\lfloor\frac{ai+b}c\rfloor =\sum\limits_{i=0}^n\sum\limits_{j=0}^{\lfloor\frac{an+b}c\rfloor-1}\left[j<\lfloor\frac{ai+b}c\rfloor\right]\\ \end{aligned}

然后又有：

[j<⌊ai+bc⌋]=[j+1<ai+b+1c]=[cj+c−b−1a<i]=[⌊cj+c−b−1a⌋<i]\begin{aligned} &\left[j<\lfloor\frac{ai+b}c\rfloor\right]\\ =&\left[j+1<\frac{ai+b+1}c\right]\\ =&\left[\frac{cj+c-b-1}a<i\right]\\ =&\left[\lfloor\frac{cj+c-b-1}a\rfloor<i\right] \end{aligned}

记 m=⌊an+bc⌋m=\lfloor\frac{an+b}c\rfloor，则有原式为：

f(a,b,c,n)=∑i=0n⌊ai+bc⌋=∑i=0n∑j=0m−1[j<⌊ai+bc⌋]=∑i=0n∑j=0m−1[⌊cj+c−b−1a⌋<i]=∑j=0m−1∑i=0n[i>⌊cj+c−b−1a⌋]=∑j=0m−1(n−⌊cj+c−b−1a⌋)=∑j=0m−1n−∑j=0m−1⌊cj+c−b−1a⌋ =nm−f(c,c−b−1,a,m−1)\begin{aligned} &f(a,b,c,n)\\ =&\sum\limits_{i=0}^n\lfloor\frac{ai+b}c\rfloor\\ =&\sum\limits_{i=0}^n\sum\limits_{j=0}^{m-1}\left[j<\lfloor\frac{ai+b}c\rfloor\right]\\ =&\sum\limits_{i=0}^n\sum\limits_{j=0}^{m-1}\left[\lfloor\frac{cj+c-b-1}a\rfloor<i \right]\\ =&\sum\limits_{j=0}^{m-1}\sum\limits_{i=0}^n\left[i>\lfloor\frac{cj+c-b-1}a\rfloor\right]\\ =&\sum\limits_{j=0}^{m-1}(n-\lfloor\frac{cj+c-b-1}a\rfloor)\\ =&\sum\limits_{j=0}^{m-1}n-\sum\limits_{j=0}^{m-1}\lfloor\frac{cj+c-b-1}a\rfloor\\\ =&nm-f(c,c-b-1,a,m-1) \end{aligned}

不断重复执行上面的两个操作直到 a=0a=0 的边界情况为止，可以利用类似于欧几里得算法 / 扩展欧几里得算法的时间复杂度分析，证明其时间复杂度为 O(log⁡min⁡(a,c))O(\log\min(a,c))。

练习

Problem 1

给定 a,b,c,na,b,c,n，计算下面表达式的值：

(∑i=0ni⌊ai+bc⌋) mod 998244353(\sum\limits_{i=0}^ni\lfloor\frac{ai+b}c\rfloor)\bmod 998244353

Sol 1

和前面的推导过程很相似。首先把问题转化为 a,b<ca,b<c 的情况：

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

然后只考虑 a,b<ca,b<c 的情况（同样的，还是记 m=⌊an+bc⌋m=\lfloor\frac{an+b}c\rfloor）：

g(a,b,c,n)=∑i=0ni⌊ai+bc⌋=∑i=0ni∑j=0m−1[j<⌊ai+bc⌋]=∑i=0ni∑j=0m−1[i>⌊cj+c−b−1a⌋]=∑j=0m−1∑i=0ni[i>⌊cj+c−b−1a⌋]=∑j=0m−1∑i=⌊cj+c−b−1a⌋+1ni=∑j=0m−112(n+⌊cj+c−b−1a⌋+1)(n−⌊cj+c−b−1a⌋)=∑j=0m−112(n2−⌊cj+c−b−1a⌋2+n−⌊cj+c−b−1a⌋)=∑j=0m−112n(n+1)−∑j=0m−112⌊cj+c−b−1a⌋2−∑j=0m−112⌊cj+c−b−1a⌋=12nm(n+1)−12∑j=0m−1⌊cj+c−b−1a⌋2−12∑j=0m−1⌊cj+c−b−1a⌋=12nm(n+1)−12h(c,c−b−1,a,m−1)−12f(c,c−b−1,a,m−1)\begin{aligned} &g(a,b,c,n)\\ =&\sum\limits_{i=0}^ni\lfloor\frac{ai+b}c\rfloor\\ =&\sum\limits_{i=0}^ni\sum\limits_{j=0}^{m-1}\left[j<\lfloor\frac{ai+b}c\rfloor \right]\\ =&\sum\limits_{i=0}^ni\sum\limits_{j=0}^{m-1}\left[i>\lfloor\frac{cj+c-b-1}a\rfloor \right]\\ =&\sum\limits_{j=0}^{m-1}\sum\limits_{i=0}^ni\left[i>\lfloor\frac{cj+c-b-1}a\rfloor\right]\\ =&\sum\limits_{j=0}^{m-1}\sum\limits_{i=\lfloor\frac{cj+c-b-1}a\rfloor+1}^ni\\ =&\sum\limits_{j=0}^{m-1}\frac12(n+\lfloor\frac{cj+c-b-1}a\rfloor+1)(n-\lfloor\frac{cj+c-b-1}a\rfloor)\\ =&\sum\limits_{j=0}^{m-1}\frac12(n^2-\lfloor\frac{cj+c-b-1}a\rfloor^2+n-\lfloor\frac{cj+c-b-1}a\rfloor)\\ =&\sum\limits_{j=0}^{m-1}\frac12n(n+1)-\sum\limits_{j=0}^{m-1}\frac12\lfloor\frac{cj+c-b-1}a\rfloor^2-\sum\limits_{j=0}^{m-1}\frac12\lfloor\frac{cj+c-b-1}a\rfloor\\ =&\frac12nm(n+1)-\frac12\sum\limits_{j=0}^{m-1}\lfloor\frac{cj+c-b-1}a\rfloor^2-\frac12\sum\limits_{j=0}^{m-1}\lfloor\frac{cj+c-b-1}a\rfloor\\ =&\frac12nm(n+1)-\frac12h(c,c-b-1,a,m-1)-\frac12f(c,c-b-1,a,m-1) \end{aligned}

其中

h(a,b,c,n)=∑i=0n⌊ai+bc⌋2h(a,b,c,n)=\sum\limits_{i=0}^n\lfloor\frac{ai+b}c\rfloor^2

现在的问题就是计算 h(a,b,c,n)h(a,b,c,n) 的值。同样考虑类欧，先转化为 a,b<ca,b<c 的情况：

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

然后同样的只考虑 a,b<ca,b<c 的情况（同样的，还是记 m=⌊an+bc⌋m=\lfloor\frac{an+b}c\rfloor）：

h(a,b,c,n)=∑i=0n⌊ai+bc⌋2=∑i=0n∑j=0m−1[j<⌊ai+bc⌋](2j+1)=∑i=0n∑j=0m−1[i>⌊cj+c−b−1a⌋](2j+1)=∑j=0m−1(2j+1)∑i=0n[i>⌊cj+c−b−1a⌋]=∑j=0m−1(2j+1)(n−⌊cj+c−b−1a⌋)=∑j=0m−12jn+∑j=0m−1n−∑j=0m−12j⌊cj+c−b−1a⌋−∑j=0m−1⌊cj+c−b−1a⌋=nm2−2∑j=0m−1⌊cj+c−b−1a⌋−∑j=0m−1⌊cj+c−b−1a⌋=nm2−2g(c,c−b−1,a,m−1)−f(c,c−b−1,a,m−1)\begin{aligned} &h(a,b,c,n)\\ =&\sum\limits_{i=0}^n\lfloor\frac{ai+b}c\rfloor^2\\ =&\sum\limits_{i=0}^n\sum\limits_{j=0}^{m-1}\left[j<\lfloor\frac{ai+b}c\rfloor\right](2j+1)\\ =&\sum\limits_{i=0}^n\sum\limits_{j=0}^{m-1}\left[i>\lfloor\frac{cj+c-b-1}a\rfloor \right](2j+1)\\ =&\sum\limits_{j=0}^{m-1}(2j+1)\sum\limits_{i=0}^n\left[i>\lfloor\frac{cj+c-b-1}a\rfloor\right]\\ =&\sum\limits_{j=0}^{m-1}(2j+1)(n-\lfloor\frac{cj+c-b-1}a\rfloor)\\ =&\sum\limits_{j=0}^{m-1}2jn+\sum\limits_{j=0}^{m-1}n-\sum\limits_{j=0}^{m-1}2j\lfloor\frac{cj+c-b-1}a\rfloor-\sum\limits_{j=0}^{m-1}\lfloor\frac{cj+c-b-1}a\rfloor\\ =&nm^2-2\sum\limits_{j=0}^{m-1}\lfloor\frac{cj+c-b-1}a\rfloor-\sum\limits_{j=0}^{m-1}\lfloor\frac{cj+c-b-1}a\rfloor\\ =&nm^2-2g(c,c-b-1,a,m-1)-f(c,c-b-1,a,m-1)\\ \end{aligned}

此时可以在 g,hg,h 两个函数之间轮换递归处理计算答案，注意到递归到不同函数的参数都是相同的，所以总时间复杂度仍然为 O(log⁡min⁡(a,c))O(\log\min(a,c))。

Problem 2

给定 a,b,ca,b,c，求不等式 ax+by≤cax+by\le c 的非负整数解 (x,y)(x,y) 的对数。

Sol 2

直接对 ax+by≤cax+by\le c 搞事情的话需要同时处理 x,yx,y 两个维度上的问题，因此考虑移项再处理，得到 0≤y≤⌊c−axb⌋0\le y\le \lfloor\frac{c-ax}b\rfloor，即对于一个固定的 xx，yy 的取值范围是 [0,⌊c−axb⌋]∩N+[0,\lfloor\frac{c-ax}b\rfloor]\cap\mathbb{N_+}。

于是该不等式的解的数量即为：

∑i=0⌊ca⌋⌊c−aib⌋+⌊ca⌋+1\sum\limits_{i=0}^{\lfloor\frac ca\rfloor}\lfloor\frac{c-ai}b\rfloor+\lfloor\frac ca\rfloor+1

于是实际上要求的核心部分就是：

∑i=0⌊ca⌋⌊−ai+cb⌋\sum\limits_{i=0}^{\lfloor\frac ca\rfloor}\lfloor\frac{-ai+c}b\rfloor

但是这个东西前面的系数是负的，直接搞会比较的难受。考虑做一个小小的转化：

∑i=0n⌊−ai+cb⌋=∑i=0n⌊−ai−cb⌋=−∑i=0n⌊ai+(b−c−1)b⌋\begin{aligned} &\sum\limits_{i=0}^n\lfloor\frac{-ai+c}b\rfloor\\ =&\sum\limits_{i=0}^n\lfloor-\frac{ai-c}b\rfloor\\ =&-\sum\limits_{i=0}^n\lfloor\frac{ai+(b-c-1)}b\rfloor\\ \end{aligned}

这个式子就是最基本的类欧形式，直接套公式即可 O(log⁡min⁡(a,b,c))O(\log \min(a,b,c)) 求解。

Problem 3

给定 n,rn,r，求 ∑d=1n(−1)⌊dr⌋\sum\limits_{d=1}^n(-1)^{\lfloor d\sqrt r\rfloor} 的值。

Sol 3

先考虑一个经典结论：

(−1)x=1−2[x mod 2=1](-1)^x=1-2[x\bmod 2=1]

然后考虑从这个结论入手来获取一些有用的信息：

(−1)x=1−2[x mod 2=1]=1−2(x−2⌊x2⌋)=1−2x+4⌊x2⌋\begin{aligned} &(-1)^x\\ =&1-2[x\bmod 2=1]\\ =&1-2(x-2\lfloor\frac x2\rfloor)\\ =&1-2x+4\lfloor\frac x2\rfloor \end{aligned}

然后考虑把这个东西带入原式：

∑d=1n(−1)⌊dr⌋=∑d=1n(1−2⌊dr⌋+4⌊⌊dr⌋2⌋)=(∑d=1n1)−(∑d=1n2⌊dr⌋)+(∑d=1n4⌊⌊dr⌋2⌋)=n−(∑d=1n2⌊dr⌋)+(∑d=1n4⌊dr2⌋)\begin{aligned} &\sum\limits_{d=1}^n(-1)^{\lfloor d\sqrt r\rfloor}\\ =&\sum\limits_{d=1}^n(1-2\lfloor d\sqrt r\rfloor+4\lfloor\frac{\lfloor d\sqrt r\rfloor}2\rfloor)\\ =&(\sum\limits_{d=1}^n1)-(\sum\limits_{d=1}^n2\lfloor d\sqrt r\rfloor)+(\sum\limits_{d=1}^n4\lfloor\frac{\lfloor d\sqrt r\rfloor}2\rfloor)\\ =&n-(\sum\limits_{d=1}^n2\lfloor d\sqrt r\rfloor)+(\sum\limits_{d=1}^n4\lfloor\frac{d\sqrt r}2\rfloor)\\ \end{aligned}

考虑换元，令 x=rx=\sqrt r，则此时考虑构造函数 γ(a,b,c,n)=∑i=1n⌊ax+bc×i⌋\gamma(a,b,c,n)=\sum\limits_{i=1}^n\lfloor\frac{ax+b}c\times i\rfloor，那么上式的答案可以表示为 n−2γ(1,0,1,n)+4γ(1,0,2,n)n-2\gamma(1,0,1,n)+4\gamma(1,0,2,n)。因此只需要用类欧把 γ\gamma 函数给表示出来即可。

这里注意到 ax+bc\frac{ax+b}c 的值是一个定值，因此容易想到对其值进行分类讨论：

1. ax+bc=1\large\frac{ax+b}c=1

此时有 γ(a,b,c,n)=∑i=1n1=n\gamma(a,b,c,n)=\sum\limits_{i=1}^n 1=n。

2. ax+bc>1\large\frac{ax+b}c>1

记 t=ax+bc,T=⌊t⌋t=\frac{ax+b}c,T=\lfloor t\rfloor，则考虑构造类欧形式：

γ(a,b,c,n)=∑i=1n⌊ti⌋=∑i=1n⌊ti−Ti+Ti⌋=∑i=1n⌊ti−Ti⌋+∑i=1nTi=∑i=1n⌊(ax+bc−T)i⌋+n(n+1)T2=γ(a,b−cT,c,n)+n(n+1)T2\begin{aligned} &\gamma(a,b,c,n)\\ =&\sum\limits_{i=1}^n\lfloor ti\rfloor\\ =&\sum\limits_{i=1}^n\lfloor ti-Ti+Ti\rfloor\\ =&\sum\limits_{i=1}^n\lfloor ti-Ti\rfloor+\sum\limits_{i=1}^nTi\\ =&\sum\limits_{i=1}^n\lfloor(\frac{ax+b}c-T)i\rfloor+\frac{n(n+1)T}2\\ =&\gamma(a,b-cT,c,n)+\frac{n(n+1)T}2 \end{aligned}

3. ax+bc<1\large\frac{ax+b}c<1

此时有 T=0T=0，无法继续使用上面的递归公式递归处理答案，因此考虑换一个方法。

γ(a,b,c,n)=∑i=1n⌊ti⌋=∑i=1n∑j=1⌊nt⌋[j<ti]=∑i=1n∑j=1⌊nt⌋[i>jt]=∑j=1⌊nt⌋∑i=1n[i>jt]=∑j=1⌊nt⌋(n−⌊jt⌋)=∑j=1⌊nt⌋(n−⌊jax+bc⌋)=∑j=1⌊nt⌋(n−⌊jcax+b⌋)=n⌊nt⌋−∑j=1⌊nt⌋⌊cax+bj⌋=n⌊nt⌋−∑j=1⌊nt⌋⌊c(ax−b)a2x2−b2j⌋=n⌊nt⌋−∑j=1⌊nt⌋⌊cax−cba2r−b2j⌋=n⌊nt⌋−γ(ca,−cb,a2r−b2,⌊nt⌋)\begin{aligned} &\gamma(a,b,c,n)\\ =&\sum\limits_{i=1}^n\lfloor ti\rfloor\\ =&\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor nt\rfloor}[j<ti]\\ =&\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor nt\rfloor}[i>\frac jt]\\ =&\sum\limits_{j=1}^{\lfloor nt\rfloor}\sum\limits_{i=1}^n[i>\frac jt]\\ =&\sum\limits_{j=1}^{\lfloor nt\rfloor}(n-\lfloor \frac jt\rfloor)\\ =&\sum\limits_{j=1}^{\lfloor nt\rfloor}\left(n-\left\lfloor\frac j{\frac{ax+b}c}\right\rfloor \right)\\ =&\sum\limits_{j=1}^{\lfloor nt\rfloor}\left(n-\left\lfloor\frac{jc}{ax+b}\right\rfloor \right)\\ =&n\lfloor nt\rfloor-\sum\limits_{j=1}^{\lfloor nt\rfloor}\left\lfloor\frac{c}{ax+b}j\right\rfloor\\ =&n\lfloor nt\rfloor-\sum\limits_{j=1}^{\lfloor nt\rfloor}\left\lfloor\frac{c(ax-b)}{a^2x^2-b^2}j\right\rfloor\\ =&n\lfloor nt\rfloor-\sum\limits_{j=1}^{\lfloor nt\rfloor}\left\lfloor\frac{cax-cb}{a^2r-b^2}j\right\rfloor\\ =&n\lfloor nt\rfloor-\gamma(ca,-cb,a^2r-b^2,\lfloor nt\rfloor) \end{aligned}

同样也得到了递归公式。简单分析可知该算法时间复杂度同样为 O(log⁡n)O(\log n) 级别，可以通过该题。

corner case

需要特殊处理 r∈N\sqrt r\in\mathbb{N} 的情况。

userId_undefined
去预览
0/2000

全部评论 3

  • userId_undefined
    Lost
    尊贵铂金传道者USACOGESP8级CSP-J一等奖CSP-S一等奖

    ddd

    2天前 来自 山东

    2
  • userId_undefined
    Lost
    尊贵铂金传道者USACOGESP8级CSP-J一等奖CSP-S一等奖

    ddd

    2天前 来自 山东

    2
  • userId_undefined
    cjdst
    尊贵铂金CSP-S一等奖代码纠察员出题人

    严肃完成大学习中

    2天前 来自 广东

    0
    • userId_undefined
      cjdst
      回复
      cjdst

      只看懂了第一步/ll

      2天前 来自 广东

      0

热门讨论