没写完，以后还会更（）
引入
给定 a,b,c,na,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 (i=0∑n ⌊cai+b ⌋)mod998244353
类欧几里得算法
考虑下面的恒等式：
⌊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 ⌊cai+b ⌋=⌊c(⌊ca ⌋c+amodc)i+(⌊cb ⌋c+bmodc) ⌋
于是我们有：
∑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} === i=0∑n ⌊cai+b ⌋i=0∑n ⌊c(⌊ca ⌋c+amodc)i+(⌊cb ⌋c+bmodc) ⌋i=0∑n ⌊c(amodc)i+bmodc ⌋+i=0∑n i⌊ca ⌋+i=0∑n ⌊cb ⌋i=0∑n ⌊c(amodc)i+bmodc ⌋+2n(n+1)⌊ca ⌋ +(n+1)⌊cb ⌋
记 f(a,b,c,n)=∑i=0n⌊ai+bc⌋f(a,b,c,n)=\sum\limits_{i=0}^n\lfloor\frac{ai+b}c\rfloorf(a,b,c,n)=i=0∑n ⌊cai+b ⌋，则有：
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 f(a,b,c,n)=f(amodc,bmodc,c,n)+2n(n+1)⌊ca ⌋ +(n+1)⌊cb ⌋
于是问题被转化为了 a,b<ca,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} i=0∑n ⌊cai+b ⌋=i=0∑n j=0∑⌊can+b ⌋−1 [j<⌊cai+b ⌋]
然后又有：
[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} === [j<⌊cai+b ⌋][j+1<cai+b+1 ][acj+c−b−1
<i][⌊acj+c−b−1 ⌋<i]
记 m=⌊an+bc⌋m=\lfloor\frac{an+b}c\rfloorm=⌊can+b ⌋，则有原式为：
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} ====== = f(a,b,c,n)i=0∑n ⌊cai+b ⌋i=0∑n j=0∑m−1 [j<⌊cai+b ⌋]i=0∑n j=0∑m−1 [⌊acj+c−b−1 ⌋<i]j=0∑m−1 i=0∑n [i>⌊acj+c−b−1
⌋]j=0∑m−1 (n−⌊acj+c−b−1 ⌋)j=0∑m−1 n−j=0∑m−1 ⌊acj+c−b−1 ⌋nm−f(c,c−b−1,a,m−1)
不断重复执行上面的两个操作直到 a=0a=0a=0 的边界情况为止，可以利用类似于欧几里得算法 / 扩展欧几里得算法的时间复杂度分析，证明其时间复杂度为 O(logmin(a,c))O(\log\min(a,c))O(logmin(a,c))。
练习
PROBLEM 1
给定 a,b,c,na,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 (i=0∑n i⌊cai+b ⌋)mod998244353
SOL 1
和前面的推导过程很相似。首先把问题转化为 a,b<ca,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} ===== g(a,b,c,n)i=0∑n i⌊cai+b ⌋i=0∑n (i⌊c(amodc)i+bmodc ⌋+i2⌊ca ⌋+i⌊cb ⌋)i=0∑n i⌊c(amodc)i+bmodc ⌋+i=0∑n i2⌊ca ⌋+i=0∑n i⌊cb ⌋i=0∑n i⌊c(amodc)i+bmodc ⌋+6n(n+1)(2n+1)⌊ca ⌋ +2n(n+1)⌊cb ⌋ g(amodc,bmodc,c,n)+6n(n+1)(2n+1)⌊ca ⌋ +2n(n+1)⌊cb ⌋
然后只考虑 a,b<ca,b<ca,b<c 的情况（同样的，还是记 m=⌊an+bc⌋m=\lfloor\frac{an+b}c\rfloorm=⌊can+b ⌋）：
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} ========== g(a,b,c,n)i=0∑n i⌊cai+b ⌋i=0∑n ij=0∑m−1 [j<⌊cai+b ⌋]i=0∑n ij=0∑m−1
[i>⌊acj+c−b−1 ⌋]j=0∑m−1 i=0∑n i[i>⌊acj+c−b−1 ⌋]j=0∑m−1 i=⌊acj+c−b−1 ⌋+1∑n ij=0∑m−1 21 (n+⌊acj+c−b−1 ⌋+1)(n−⌊acj+c−b−1 ⌋)j=0∑m−1 21 (n2−⌊acj+c−b−1 ⌋2+n−⌊acj+c−b−1 ⌋)j=0∑m−1 21 n(n+1)−j=0∑m−1 21 ⌊acj+c−b−1 ⌋2−j=0∑m−1 21 ⌊acj+c−b−1 ⌋21 nm(n+1)−21 j=0∑m−1 ⌊acj+c−b−1 ⌋2−21 j=0∑m−1 ⌊acj+c−b−1 ⌋21
nm(n+1)−21 h(c,c−b−1,a,m−1)−21 f(c,c−b−1,a,m−1)
其中
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)=i=0∑n ⌊cai+b ⌋2
现在的问题就是计算 h(a,b,c,n)h(a,b,c,n)h(a,b,c,n) 的值。同样考虑类欧，先转化为 a,b<ca,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} ===== h(a,b,c,n)i=0∑n ⌊cai+b ⌋2i=0∑n ⌊c(⌊ca ⌋c+amodc)i+(⌊cb ⌋c+bmodc)
⌋2(i=0∑n ⌊ca ⌋i+i=0∑n ⌊cb ⌋+⌊c(amodc)i+bmodc ⌋)2⌊ca ⌋2i=0∑n i2+2⌊ca ⌋⌊cb ⌋i=0∑n i+⌊cb ⌋2(n+1)+2⌊ca ⌋i=0∑n i⌊c(amodc)i+bmodc ⌋+2⌊cb ⌋i=0∑n ⌊c(amodc)i+bmodc ⌋+i=0∑n ⌊c(amodc)i+bmodc ⌋2⌊ca ⌋26n(n+1)(2n+1) +2⌊ca ⌋⌊cb ⌋2n(n+1) +⌊cb ⌋2(n+1)+2⌊ca ⌋i=0∑n i⌊c(amodc)i+(bmodc) ⌋+2⌊cb ⌋i=0∑n ⌊c(amodc)i+bmodc
⌋+h(amodc,bmodc,c,n)
然后同样的只考虑 a,b<ca,b<ca,b<c 的情况（同样的，还是记 m=⌊an+bc⌋m=\lfloor\frac{an+b}c\rfloorm=⌊can+b ⌋）：
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} ======== h(a,b,c,n)i=0∑n ⌊cai+b ⌋2i=0∑n j=0∑m−1 [j<⌊cai+b ⌋](2j+1)i=0∑n j=0∑m−1 [i>⌊acj+c−b−1 ⌋](2j+1)j=0∑m−1 (2j+1)i=0∑n [i>⌊acj+c−b−1 ⌋]j=0∑m−1 (2j+1)(n−⌊acj+c−b−1 ⌋)j=0∑m−1 2jn+j=0∑m−1 n−j=0∑m−1 2j⌊acj+c−b−1 ⌋−j=0∑m−1 ⌊acj+c−b−1
⌋nm2−2j=0∑m−1 ⌊acj+c−b−1 ⌋−j=0∑m−1 ⌊acj+c−b−1 ⌋nm2−2g(c,c−b−1,a,m−1)−f(c,c−b−1,a,m−1)
此时可以在 g,hg,hg,h 两个函数之间轮换递归处理计算答案，注意到递归到不同函数的参数都是相同的，所以总时间复杂度仍然为 O(logmin(a,c))O(\log\min(a,c))O(logmin(a,c))。
PROBLEM 2
给定 a,b,ca,b,ca,b,c，求不等式 ax+by≤cax+by\le cax+by≤c 的非负整数解 (x,y)(x,y)(x,y) 的对数。
SOL 2
直接对 ax+by≤cax+by\le cax+by≤c 搞事情的话需要同时处理 x,yx,yx,y 两个维度上的问题，因此考虑移项再处理，得到 0≤y≤⌊c−axb⌋0\le y\le \lfloor\frac{c-ax}b\rfloor0≤y≤⌊bc−ax ⌋，即对于一个固定的 xxx，yyy 的取值范围是 [0,⌊c−axb⌋]∩N+[0,\lfloor\frac{c-ax}b\rfloor]\cap\mathbb{N_+}[0,⌊bc−ax ⌋]∩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∑⌊ac ⌋ ⌊bc−ai ⌋+⌊ac ⌋+1
于是实际上要求的核心部分就是：
∑i=0⌊ca⌋⌊−ai+cb⌋\sum\limits_{i=0}^{\lfloor\frac ca\rfloor}\lfloor\frac{-ai+c}b\rfloor i=0∑⌊ac ⌋ ⌊b−ai+c ⌋
但是这个东西前面的系数是负的，直接搞会比较的难受。考虑做一个小小的转化：
∑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} == i=0∑n ⌊b−ai+c ⌋i=0∑n ⌊−bai−c ⌋−i=0∑n ⌊bai+(b−c−1) ⌋
这个式子就是最基本的类欧形式，直接套公式即可 O(logmin(a,b,c))O(\log \min(a,b,c))O(logmin(a,b,c)) 求解。
PROBLEM 3
给定 n,rn,rn,r，求 ∑d=1n(−1)⌊dr⌋\sum\limits_{d=1}^n(-1)^{\lfloor d\sqrt r\rfloor}d=1∑n (−1)⌊dr ⌋ 的值。
SOL 3
先考虑一个经典结论：
(−1)x=1−2[x mod 2=1](-1)^x=1-2[x\bmod 2=1] (−1)x=1−2[xmod2=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} === (−1)x1−2[xmod2=1]1−2(x−2⌊2x ⌋)1−2x+4⌊2x ⌋
然后考虑把这个东西带入原式：
∑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} === d=1∑n (−1)⌊dr ⌋d=1∑n (1−2⌊dr
⌋+4⌊2⌊dr ⌋ ⌋)(d=1∑n 1)−(d=1∑n 2⌊dr ⌋)+(d=1∑n 4⌊2⌊dr ⌋ ⌋)n−(d=1∑n 2⌊dr ⌋)+(d=1∑n 4⌊2dr ⌋)
考虑换元，令 x=rx=\sqrt rx=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γ(a,b,c,n)=i=1∑n ⌊cax+b ×i⌋，那么上式的答案可以表示为 n−2γ(1,0,1,n)+4γ(1,0,2,n)n-2\gamma(1,0,1,n)+4\gamma(1,0,2,n)n−2γ(1,0,1,n)+4γ(1,0,2,n)。因此只需要用类欧把 γ\gammaγ 函数给表示出来即可。
这里注意到 ax+bc\frac{ax+b}ccax+b 的值是一个定值，因此容易想到对其值进行分类讨论：
1. ax+bc=1\large\frac{ax+b}c=1cax+b =1
此时有 γ(a,b,c,n)=∑i=1n1=n\gamma(a,b,c,n)=\sum\limits_{i=1}^n 1=nγ(a,b,c,n)=i=1∑n 1=n。
2. ax+bc>1\large\frac{ax+b}c>1cax+b >1
记 t=ax+bc,T=⌊t⌋t=\frac{ax+b}c,T=\lfloor t\rfloort=cax+b ,T=⌊t⌋，则考虑构造类欧形式：
γ(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} ===== γ(a,b,c,n)i=1∑n ⌊ti⌋i=1∑n ⌊ti−Ti+Ti⌋i=1∑n ⌊ti−Ti⌋+i=1∑n Tii=1∑n ⌊(cax+b −T)i⌋+2n(n+1)T γ(a,b−cT,c,n)+2n(n+1)T
3. ax+bc<1\large\frac{ax+b}c<1cax+b <1
此时有 T=0T=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} =========== γ(a,b,c,n)i=1∑n ⌊ti⌋i=1∑n j=1∑⌊nt⌋ [j<ti]i=1∑n j=1∑⌊nt⌋ [i>tj ]j=1∑⌊nt⌋ i=1∑n [i>tj ]j=1∑⌊nt⌋ (n−⌊tj ⌋)j=1∑⌊nt⌋ (n−⌊cax+b j ⌋)j=1∑⌊nt⌋ (n−⌊ax+bjc ⌋)n⌊nt⌋−j=1∑⌊nt⌋ ⌊ax+bc j⌋n⌊nt⌋−j=1∑⌊nt⌋ ⌊a2x2−b2c(ax−b) j⌋n⌊nt⌋−j=1∑⌊nt⌋
⌊a2r−b2cax−cb j⌋n⌊nt⌋−γ(ca,−cb,a2r−b2,⌊nt⌋)
同样也得到了递归公式。简单分析可知该算法时间复杂度同样为 O(logn)O(\log n)O(logn) 级别，可以通过该题。
corner case
需要特殊处理 r∈N\sqrt r\in\mathbb{N}r ∈N 的情况。
