求$\sum_{i=0}^{n} \lfloor \frac{a*i+b}{c} \rfloor$

當$c\leq a$或$c \leq b$時

　　$$\lfloor \frac{a}{c} \rfloor * \frac{n*(n+1)}{2}+\lfloor \frac{b}{c} \rfloor*(n+1)+\sum_{i=0}^{n} \lfloor \frac{(a \mod c) *i+(b \mod c)}{c} \rfloor$$

否則令$m=\lfloor \frac{a*i+b}{c} \rfloor-1$

$$=\sum_{i=0}^{n} \sum_{j=0}^{m}1$$

$$=\sum_{i=0}^{n} \sum_{j=0}^{m} [j<\lfloor \frac{a*i+b}{c} \rfloor]$$

$$=\sum_{i=0}^{n} \sum_{j=0}^{m} [j<\lceil \frac{a*i+b-c+1}{c} \rfloor]$$

$$=\sum_{i=0}^{n} \sum_{j=0}^{m} [c*j < a*i+b-c+1]$$

$$=\sum_{j=0}^{m} \sum_{i=0}^{n} [a*i>c*j-b+c-1]$$

$$=\sum_{j=0}^{m} \sum_{i=0}^{n} [i>\lfloor \frac{c*j-b+c-1}{a} \rfloor]$$

$$=\sum_{j=0}^{m} n-\lfloor \frac{c*j-b+c-1}{a} \rfloor$$

$$=n*(m+1)-\sum_{j=0}^{m} \lfloor \frac{c*j-b+c-1}{a} \rfloor$$

我們可以遞歸處理，復雜度和歐幾里得算法相同。

轉載于:https://www.cnblogs.com/iamqzh233/p/11027688.html

總結

以上是生活随笔為你收集整理的类欧几里得算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。