锐客网

  1. 首页 > it技术 > >

题解|类欧几里得算法（部分）

题解---数论

##Preface
欧几里得算法，就是辗转相除法。
gcd(i,j)=gcd(j,i%j)
##定义
定义函数
F ( a , b , c , n ) = ∑ i = 0 n ? a i + b c ? F(a,b,c,n)=\sum\limits_{i=0}^n \lfloor {ai+b\over c}\rfloor F(a,b,c,n)=i=0∑n??cai+b??
##推导一波
显然当 a ≥ c a\geq c a≥c或者 b ≥ c b\geq c b≥c时， F ( a , b , c , n ) = ∑ i = 0 n ( ? ( a m o d     c ) i + ( b m o d     c ) c ? + ? a c ? i + ? b c ? F(a,b,c,n)=\sum\limits_{i=0}^n (\lfloor {(a\mod c)i+(b \mod c)\over c}\rfloor+\lfloor{a\over c}\rfloor i+\lfloor{b\over c}\rfloor F(a,b,c,n)=i=0∑n?(?c(amodc)i+(bmodc)??+?ca??i+?cb??
= F ( a % c , b % c , c , n ) + ? a c ? ( n + 1 ) n / 2 + ? b c ? ( n + 1 ) =F(a\%c,b\%c,c,n)+\lfloor{a\over c}\rfloor (n+1)n/2+\lfloor{b\over c}\rfloor (n+1) =F(a%c,b%c,c,n)+?ca??(n+1)n/2+?cb??(n+1)
若当a,b均小于c怎么办？
据大佬说转换成几何意义就是一条直线与x轴、y轴以及 x = n x=n x=n围成的直角梯形中的整点个数
枚举纵线，
原式可化为
设 m = ? a n + b c ? m=\lfloor {an+b\over c}\rfloor m=?can+b??就是上面式子i=n时的数
枚举每个数
F ( a , b , c , n ) = ∑ i = 0 n ∑ j = 1 m [ ? a i + b c ? ≥ j ] F(a,b,c,n)=\sum\limits_{i=0}^{n}\sum\limits_{j=1}^{m}[\lfloor {ai+b\over c}\rfloor\geq j] F(a,b,c,n)=i=0∑n?j=1∑m?[?cai+b??≥j]
尽量化成j=0
= ∑ i = 0 n ∑ j = 0 m ? 1 [ ? a i + b c ? ≥ j + 1 ] =\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m-1}[\lfloor {ai+b\over c}\rfloor\geq j+1] =i=0∑n?j=0∑m?1?[?cai+b??≥j+1]
大于等于下整除和不整除是一样的
= ∑ i = 0 n ∑ j = 0 m ? 1 [ ( a i + b c ) ≥ j + 1 ] =\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m-1}[({ai+b\over c})\geq j+1] =i=0∑n?j=0∑m?1?[(cai+b?)≥j+1]
变换一下
= ∑ i = 0 n ∑ j = 0 m ? 1 [ ( a i ≥ c j + c ? b ] =\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m-1}[(ai\geq cj+c-b] =i=0∑n?j=0∑m?1?[(ai≥cj+c?b]
= ∑ i = 0 n ∑ j = 0 m ? 1 [ ( i ≥ ( c j + c ? b ) a ] =\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m-1}[(i\geq {(cj+c-b)\over a}] =i=0∑n?j=0∑m?1?[(i≥a(cj+c?b)?]
注意这里没有取整
大于等于，因为左边是整数
分子减1，符号变成大于
= ∑ i = 0 n ∑ j = 0 m ? 1 [ ( i > ( c j + c ? b ? 1 ) a ] =\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{m-1}[(i> {(cj+c-b-1)\over a}] =i=0∑n?j=0∑m?1?[(i>a(cj+c?b?1)?]
交换主体
= ∑ j = 0 m ? 1 ∑ i = 0 n [ ( i > ( c j + c ? b ? 1 ) a ] =\sum\limits_{j=0}^{m-1}\sum\limits_{i=0}^{n}[(i> {(cj+c-b-1)\over a}] =j=0∑m?1?i=0∑n?[(i>a(cj+c?b?1)?]
然后里面的sigma可以撤掉
= ∑ j = 0 m ? 1 n ? ( c j + c ? b ? 1 ) a =\sum\limits_{j=0}^{m-1}n- {(cj+c-b-1)\over a} =j=0∑m?1?n?a(cj+c?b?1)?
= n m ? ∑ j = 0 m ? 1 ( c j + c ? b ? 1 ) a =nm-\sum\limits_{j=0}^{m-1}{(cj+c-b-1)\over a} =nm?j=0∑m?1?a(cj+c?b?1)?
所以 F ( a , b , c , n ) = n m ? F ( c , c ? b ? 1 , a , m ? 1 ) F(a,b,c,n)=nm-F(c,c-b-1,a,m-1) F(a,b,c,n)=nm?F(c,c?b?1,a,m?1)
如果只看a,c二维，变换是和欧几里得算法一样的
复杂度也和欧几里得算法一样
可以递归处理
边界条件是a=0，式子很明显。
g和h本蒟蒻并不会推，可以看看大佬的BLOG
【题解|类欧几里得算法（部分）】##模版

LL fd(LL a,LL b,LL c,LL n) { if(a==0) return((b/c)*(n+1)); if(a>=c||b>=c) return fd(a%c,b%c,c,n)+(a/c)*n*(n+1)/2+(b/c)*(n+1); LL m=(a*n+b)/c; LL v=fd(c,c-b-1,a,m-1); return n*m-v; }

    推荐阅读


    上一篇：rk3128 android4.4 平台内核驱动分析

    下一篇：Android|Android 高德地图 Polyline 实时绘制行动轨迹