本文主要是介绍阿凡达（类欧几里得算法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目
二、解法
由于 n n n很大，但是操作数很小，且一开始没有初值，很容易想到动态开点，时间复杂度 O ( n log n ) O(n\log n) O(nlogn)。
剩下的问题是如何计算一个修改段内的和，注意到 ( i − l + 1 ) ⋅ x % y = ( i − l + 1 ) ⋅ x + ( i − l + 1 ) ⋅ x y (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(\log n) O(logn)，下面详细讲一下这个算法。
类欧几里得算法一般用于解决此类问题： f ( a , b , c , n ) = ∑ i = 0 n i a + b c f(a,b,c,n)=\sum_{i=0}^n \frac{ia+b}{c} f(a,b,c,n)=∑i=0ncia+b，给定 a , b , c , n a,b,c,n a,b,c,n求 f f f，下面给出算法过程及推导。
当 a ≥ c o r b ≥ c 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 ) + a c n ( n + 1 ) 2 + ( n + 1 ) 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)+ca2n(n+1)+(n+1)cb
当 a , b ≤ c a,b\leq c a,b≤c，设 m = a n + b c m=\frac{an+b}{c} m=can+b，我们开始推式子：
f ( a , b , c , n ) = ∑ i = 0 n ∑ j = 0 m − 1 [ j < i a + b c ] 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∑nj=0∑m−1[j<cia+b] = ∑ j = 0 m − 1 ∑ i = 0 n [ i > c j − b + c − 1 a ] =\sum_{j=0}^{m-1}\sum_{i=0}^n[i>\frac{cj-b+c-1}{a}] =j=0∑m−1i=0∑n[i>acj−b+c−1]上面那一步怎么来的呢？我们对括号内的内容做推导：
j < a i + b c j<\frac{ai+b}{c} j<cai+b j ≤ a i + b c − 1 j\leq \frac{ai+b}{c}-1 j≤cai+b−1 c j ≤ a i + b − c cj\leq ai+b-c cj≤ai+b−c c j < a i + b − c + 1 cj<ai+b-c+1 cj<ai+b−c+1 i > c j − b + c − 1 a i>\frac{cj-b+c-1}{a} i>acj−b+c−1然后就推出来了，我们继续推导：
= ∑ j = 0 m − 1 n − c j − b + c − 1 a =\sum_{j=0}^{m-1}n-\frac{cj-b+c-1}{a} =j=0∑m−1n−acj−b+c−1 = n m − f ( c , c − b − 1 , a , m − 1 ) =nm-f(c,c-b-1,a,m-1) =nm−f(c,c−b−1,a,m−1)发现上述算法过程类似于辗转相除法，故时间复杂度为 log \log log。
咕咕咕这篇关于阿凡达（类欧几里得算法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
