类欧几里得算法

类欧几里得

? \(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\)。

每次进行以下操作

1. \(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\)是有影响的，但是因为操作过程中的处理，也可以把他变成无影响（具体见下）

2. 考虑递归下去，\((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}\)

3. 第一次进入递归的时候要先把\((a*0+b)/c\)个\(A\)的影响提出来，而后面因为每次都提出了第一个\(A\)及其之前的\(B\)，所以相当于把每次\((a*0+b)/c\)的影响提出来了，所以递归的时候可以直接\(b\%=c\)

类欧几里得算法

原文：https://www.cnblogs.com/fruitea/p/12408849.html