阿凡达（类欧几里得算法）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了阿凡达（类欧几里得算法），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1699字，纯文字阅读大概需要3分钟。

内容图文

一、题目

二、解法

由于$n$n很大，但是操作数很小，且一开始没有初值，很容易想到动态开点，时间复杂度$O(n\log n)$O(nlogn)。

剩下的问题是如何计算一个修改段内的和，注意到$(i-l+1)\cdot x\% y=(i-l+1)\cdot x+\frac{(i-l+1)\cdot x}{y}$(i?l+1)?x%y=(i?l+1)?x+y(i?l+1)?x?（本题解中的除号均为整除），前者等差数列，后者用经典的类欧几里得算法求和，总时间复杂度$O(\log n)$O(logn)，下面详细讲一下这个算法。

类欧几里得算法一般用于解决此类问题：$f(a,b,c,n)=\sum_{i=0}^n \frac{ia+b}{c}$f(a,b,c,n)=∑i=0n?cia+b?，给定$a,b,c,n$a,b,c,n求$f$f，下面给出算法过程及推导。

当$a\geq c\space or\space b\geq c$a≥c or b≥c时，$f(a,b,c,n)=f(a\%c,b\%c,c,n)+\frac{a}{c}\frac{n(n+1)}{2}+(n+1)\frac{b}{c}$f(a,b,c,n)=f(a%c,b%c,c,n)+ca?2n(n+1)?+(n+1)cb?

当$a,b\leq c$a,b≤c，设$m=\frac{an+b}{c}$m=can+b?，我们开始推式子：
$f(a,b,c,n)=\sum_{i=0}^n\sum_{j=0}^{m-1}[j<\frac{ia+b}{c}]$f(a,b,c,n)=i=0∑n?j=0∑m?1?[j<cia+b?]$=\sum_{j=0}^{m-1}\sum_{i=0}^n[i>\frac{cj-b+c-1}{a}]$=j=0∑m?1?i=0∑n?[i>acj?b+c?1?]上面那一步怎么来的呢？我们对括号内的内容做推导：
$j<\frac{ai+b}{c}$j<cai+b?$j\leq \frac{ai+b}{c}-1$j≤cai+b??1$cj\leq ai+b-c$cj≤ai+b?c$cj<ai+b-c+1$cj<ai+b?c+1$i>\frac{cj-b+c-1}{a}$i>acj?b+c?1?然后就推出来了，我们继续推导：
$=\sum_{j=0}^{m-1}n-\frac{cj-b+c-1}{a}$=j=0∑m?1?n?acj?b+c?1?$=nm-f(c,c-b-1,a,m-1)$=nm?f(c,c?b?1,a,m?1)发现上述算法过程类似于辗转相除法，故时间复杂度为$\log$log。

咕咕咕

• 点赞
• 收藏
• 分享
• • 文章举报

C202044zxy 发布了209 篇原创文章 · 获赞 12 · 访问量 4635 私信 关注

内容总结

以上是互联网集市为您收集整理的阿凡达（类欧几里得算法）全部内容，希望文章能够帮你解决阿凡达（类欧几里得算法）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---