首页 / 算法 / 类欧几里得算法浅谈(部分)
类欧几里得算法浅谈(部分)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了类欧几里得算法浅谈(部分),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1998字,纯文字阅读大概需要3分钟。
内容图文
![类欧几里得算法浅谈(部分)](/upload/InfoBanner/zyjiaocheng/855/59d4a0d91ffc457c84ab801bbbcbf7f6.jpg)
学习类欧几里得算法,因为是蒟蒻,感觉网上很多都看不懂,所以自己写一篇快活快活
第一类求和式:
\(F(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{a*i+b}{c}\rfloor\)
对于这样形式的求和,我们有以下的推导:
1.当\(a>=c\)并且\(b>=c\)时,我们有:
对于\(\lfloor\frac{a}{c}\rfloor\),
它实际等价于\(\lfloor\frac{a\mod c}{c}\rfloor+\lfloor\frac{a}{c}\rfloor\),
于是对于原先的式子,我们可以推出:
\(F(a,b,c,d,n)=\sum_{i=0}^n\lfloor\frac{a*i+b}{c}\rfloor\) =\(\sum_{i=0}^n(\lfloor\frac{a\mod c*i+b\mod c}{c}\rfloor+\lfloor\frac{a*i}{c}\rfloor+\lfloor\frac{b}{c}\rfloor)\)
进一步化为递归的形式就是:
\(F(a\%c,b\%c,c,n)+\frac{(n+1)n}{2}*\lfloor\frac{a}{c}\rfloor+(n+1)*\lfloor\frac{b}{c}\rfloor\)
2.当\(a<c\)或者\(b<c\)时我们有:
我们观察可以很容易的发现,原先的和式的右边一大堆,去掉下取整实际上表示出来就是一条直线,即:
\(F=kx+b\),(\(k=\frac{a}{c},b=\frac{b}{c})\),
然后我们就可以轻轻松松的画出一个一次函数的图像,在坐标系里表现出的就是一个直角梯形,函数的定义域\(D\in[0,n]\),函数的值域\(Z\in[b,m]\),其中令\(m=\frac{a*n+b}{c}\),也就是当\(i\)等于\(n\)时的值.我们要求定义域内函数值的和,自然就是求积分,也就是这个直角梯形的面积.然后加上下整除符号,我们需要求出的就是这个梯形内整点的个数.
我们枚举所有整点的纵坐标,就有:
\(F=\sum_{i=0}{n}\sum_{j=1}{m}[\lfloor\frac{a*i+b}{c}\rfloor>=j]\)
\(=\sum_{i=0}{n}\sum_{j=0}{m-1}[\lfloor\frac{a*i+b}{c}\rfloor>=j+1]\)
对于\([\lfloor\frac{a*i+b}{c}\rfloor>=j+1]\),我们知道,大于等于去掉下整除依旧成立,于是
\(=\sum_{i=0}^{n}\sum_{j=0}^{m-1}[(\frac{a*i+b}{c})>=j+1]\)
将分母乘过去,\(b\)移过去:
\(=\sum_{i=0}^{n}\sum_{j=0}^{m-1}[a*i>=j*c+c-b]\)
\(a\)除过去:
\(=\sum_{i=0}^{n}\sum_{j=0}^{m-1}[i>=\frac{(j*c+c-b)}{a}]\)
我们注意到,\(j\)的变化与\(i\)是无关的,于是我们可以将两个\(\sum\)交换
\(=\sum_{j=0}^{m-1}\sum_{i=0}^{n}[i>=\frac{(j*c+c-b)}{a}]\)
\(=\sum_{j=0}^{m-1}\sum_{i=0}^{n}[i>\frac{(j*c+c-b-1)}{a}]\)
(分子减一,去掉等号)
去掉内层\(sigma\):
\(=\sum_{j=0}^{m-1} n-\frac{(j*c+c-b-1)}{a}\)
(这个显然等价)
\(=n*m-\sum_{j=0}^{m-1} \frac{(j*c+c-b-1)}{a}\)
老规矩,转换成递归形式:
\(=n*m-F(c,c-b-1,a,m-1)\)
(完)
(待补)
内容总结
以上是互联网集市为您收集整理的类欧几里得算法浅谈(部分)全部内容,希望文章能够帮你解决类欧几里得算法浅谈(部分)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。