类欧几里得算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了类欧几里得算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2366字,纯文字阅读大概需要4分钟。
内容图文
![类欧几里得算法](/upload/InfoBanner/zyjiaocheng/640/dcedc1a32d0e4cd0bb39363cdebb12a0.jpg)
类欧几里得
? \(e.g.\) 求\(\sum\limits_{x=1}^nA^xB^{\lfloor\frac{ax+b}{c}\rfloor}\)
? 把柿子转化成一个操作序列,对于一条直线(左上到右下),碰到一条\(y=n\) 的横线进行一次操作U,碰到一条\(x=n\)的竖线进行一次操作\(R\),碰到整点进行一次操作\(UR\)。两个操作序列合并就是把前一个的贡献加到后一个序列的答案里(有点像cdq分治?),需要信息支持快速合并。
? 像例子中的两个操作就是 \(U:curB*=B\ \ \ \ \ R:curA*=A,sum+=curA*curB\)
具体过程
设函数\(solve(n,a,b,c,A,B)\)
表示值域为\(n\),直线为\(y=\lfloor \frac{ax+b}{c}\rfloor\)横坐标+1填一个\(B\)操作序列,纵坐标+1填一个\(A\)操作序列。\(A,B\)从1开始标号。
可以得到:共有\(n\)个\(B\),第\(i\)个\(B\)前面共有\(\lfloor \frac{ai+b}{c} \rfloor\)个\(A\)。
每次进行以下操作
\(a->a\%c,b->b\%c\)
\(e.g.\) \(solve(3,5,1,3,A,B)->solve(3,2,1,3,A',B')\)
? \(AABABAAB->ABBAB\)
- \(a\%=c\)带来的变化:\(B'=A^{a\over c}B\)
- \(b\%=c\)无影响:
- \(i>1\)时,考虑第\(i\)个\(B\)和第\(i-1\)个\(B\),他们两个之间的\(A\)有\(\lfloor\frac{ai+b}{c}\rfloor-\lfloor\frac{a(i-1)+b}{c}\rfloor=\lfloor{a\over c}\rfloor\)个,所以\(b\%=c\)无影响
- 如果\(i=1\),\(B\)前面就有\(\lfloor\frac{a+b}{c}\rfloor\)个\(A\),看起来\(b%=c\)是有影响的,但是因为操作过程中的处理,也可以把他变成无影响(具体见下)
考虑递归下去,\((A,B)->(B,A)\)
推导:考虑第\(x\)个\(A\)和其之后第一个\(B\),假设是序列中的第\(y\)个\(B\)(推的时候因为x,y为整数,所以一些向上向下取整是可以直接加或者直接去的)
第\(i\)个\(B\)之前共有\(\lfloor\frac{ai+b}{c}\rfloor\)个\(A\)
\[x\le \lfloor\frac{ay+b}{c}\rfloor\]
\[x\le \frac{ay+b}{c}\]
\[\frac{cx-b}{a}\le y\]
\[\lceil\frac{cx-b}{a}\rceil\le y\]
\[\lfloor\frac{cx-b+a-1}{a}\rfloor\le y\]
\[\lfloor\frac{cx-b-1}{a}\rfloor< y\]
所以第\(i\)个\(A\)之前共有\(\lfloor\frac{ci-b-1}{a}\rfloor\)个\(B\)- 当\(i=0\)时,\(\lfloor\frac{ci-b-1}{a}\rfloor<0\),所以要特殊考虑第一个\(A\),具体做法是\(\lfloor\frac{ci-b-1}{a}\rfloor->\lfloor\frac{c(i+1)-b-1}{a}\rfloor\),\(A\)从0开始标号,然后再把第1个\(A\)(即现在的第0个\(A\))提出来
最后一个\(A\)之后的\(B\)也要特殊考虑
令\(m=\lfloor \frac{a*n+b}{c}\rfloor,cnt=n-\lfloor\frac{c*m-b-1}{a}\rfloor\) (\(A\)的数量,最后一个\(A\)之后的\(B\)的数量),
则\(solve(n,a,b,c,A,B)-> B^{\lfloor\frac{c-b-1}{a}\rfloor}+A+solve(m-1,c,c-b-1,a,B,A)+B^{cnt}\)
第一次进入递归的时候要先把\((a*0+b)/c\)个\(A\)的影响提出来,而后面因为每次都提出了第一个\(A\)及其之前的\(B\),所以相当于把每次\((a*0+b)/c\)的影响提出来了,所以递归的时候可以直接\(b\%=c\)
内容总结
以上是互联网集市为您收集整理的类欧几里得算法全部内容,希望文章能够帮你解决类欧几里得算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。