类欧几里得算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了类欧几里得算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1893字，纯文字阅读大概需要3分钟。
内容图文
类欧几里得算法
我们要求下面的函数：
\[
F(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{a*i+b}{c}\rfloor
\]
我们的方法是分两类情况递归下去求解。
边界条件：\(a=0\)是，\(F=(n+1)\lfloor \frac{b}{c} \rfloor\)。
1.\(a\geq c\)或\(b\geq c\)：
首先我们有如下的变换：
\[
\begin{align}
\lfloor\frac{a*i+b}{c} \rfloor&=\lfloor\frac{a*i+b\bmod c}{c} \rfloor
+\lfloor\frac{b}{c} \rfloor \&=\lfloor\frac{(a*i) \bmod c+b\bmod c}{c} \rfloor +\lfloor\frac{a*i}{c} \rfloor
+\lfloor\frac{b}{c} \rfloor \&=\lfloor\frac{(a\bmod c*i)\bmod c+b\bmod c}{c} \rfloor +i*\lfloor\frac{a}{c}\rfloor+\lfloor\frac{a\bmod c*i}{c} \rfloor
+\lfloor\frac{b}{c} \rfloor \&=\lfloor\frac{a\bmod c*i+b\bmod c}{c} \rfloor +
i*\lfloor\frac{a}{c}\rfloor
+\lfloor\frac{b}{c} \rfloor \\end{align}
\]
设：
\[
a=x*c+y
\]
则：
\[
\lfloor\frac{a}{c} \rfloor=\lfloor\frac{y}{c}\rfloor+\frac{x*c}{c}
\]
这些公式都可以用这个公式来证明（或者感性理解）。
所以我们得到：
\[
F(a,b,c,n)=F(a\bmod c,b\bmod c,c,n)+\frac{n(n+1)}{2}\lfloor\frac{a}{c}\rfloor+(n+1)\lfloor\frac{b}{c}\rfloor
\]
2.\(a<c\)且\(b<c\)：
首先我们要知道：\(\lfloor a\rfloor\)实际上就是\(\leq a\)的正整数。
然后直接大力推式子：
设\(m=\lfloor\frac{a*n+b}{c} \rfloor\)
\[
\begin{align}
F&=\sum_{i=0}^n\sum_{j=1}^m[\lfloor\frac{a*i+b}{c} \rfloor \geq j]\&=\sum_{i=0}^n\sum_{j=0}^{m-1} [\lfloor\frac{a*i+b}{c} \rfloor \geq j+1]\&=\sum_{i=0}^n\sum_{j=0}^{m-1}[\frac{a*i+b}{c}\geq j+1]\&=\sum_{j=0}^{m-1}\sum_{i=0}^{n}[i\geq \frac{j*c+c-b}{a}]\\end{align}
\]
因为：
\[
x\geq \lfloor \frac{a}{c} \rfloor\\Rightarrow x>\lfloor\frac{a-1}{c}\rfloor
\]
所以：
\[
\begin{align}
F
&=\sum_{j=0}^{m-1}\sum_{i=0}^{n}[i\geq \frac{j*c+c-b}{a}]\&=\sum_{j=0}^{m-1}\sum_{i=0}^{n}[i> \frac{j*c+c-b-1}{a}]\&=\sum_{j=0}^{m-1}n-\lfloor\frac{j*c+c-b-1}{a} \rfloor\&=n*m-\sum_{j=0}^{m-1}\lfloor\frac{j*c+c-b-1}{a} \rfloor
\end{align}
\]
于是我们又得到了：
\[
F(a,b,c,n)=n*m-F(c,c-b-1,a,m-1)\\]
其他几种就不会了。
内容总结
以上是互联网集市为您收集整理的类欧几里得算法全部内容，希望文章能够帮你解决类欧几里得算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。