PopHirasawa's Blog HomeArchivesTagsCategoriesLinksAbout
EXGCD
|算法数学
Word count: 1.3k|Reading time: 7 min
EXGCD

用于解形如ax+by=gcd（a，b）方程的通解

1
2
3
4
5
6
7
8
9
10
11
12
13
void exgcd(int &x,int &y,int a,int b)
{
    if(!b)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(x,y,b,a%b);
    int t=x;
    x=y;
    y=t-a/b*y;
}

也可以解出ax+by=c gcd（a，b）|c的解

上方参数还是gcd（a，b） 解出后x2=x*c/gcd（a，b） y2=y*c/gcd（a，b）

通解为：

{(x, y) | x = x2 + k * b / gcd(a, b)， y = y2 - k * a / gcd(a, b), k ∈ z}

特别的 gcd（a，b）等于1时

相当于求ax=1（modb） 为a在b下的逆元（不用b是质数） 解出x后用 x=（x%b+b）%b求出在0-b范围内的x即为逆元

类欧几里得

当我们要计算形如

∑i=0n⌊ai+bc⌋ \sum_{i=0}^n\lfloor \frac{ai+b}{c}\rfloor

且a，b>=0,c>0时
可以使用类欧算法。

首先有以下公式

⌈ab⌉=⌊a+b−1b⌋\lceil \frac{a}{b}\rceil = \lfloor \frac{a+b-1}{b}\rfloor

⌊ab⌋=⌈a−b+1b⌉\lfloor\frac{a}{b}\rfloor = \lceil \frac{a-b+1}{b}\rceil

挺容易推的：关于1式，如果 a % b != 0,那么右边就会比左边大1，2式原理相同。

然后开始推（？
我们令

F(a,b,c,n)=∑i=0n⌊ai+bc⌋F(a,b,c,n)=\sum_{i=0}^n\lfloor \frac{ai+b}{c}\rfloor

a≥c⇒∑i=0n⌊ai+bc⌋=∑i=0n(⌊a%c×i+bc⌋+⌊ac⌋i)=∑i=0n⌊a%c×i+bc⌋+⌊ac⌋n×(n+1)2{a}\geq{c}\Rightarrow\sum_{i=0}^n\lfloor \frac{ai+b}{c}\rfloor=\sum_{i=0}^n(\lfloor \frac{a\%c\times i+b}{c}\rfloor+\lfloor\frac{a}{c}\rfloor i)=\sum_{i=0}^n\lfloor \frac{a\%c\times i+b}{c}\rfloor+\lfloor\frac{a}{c}\rfloor\frac{n\times (n+1)}{2}

b≥c⇒∑i=0n⌊ai+bc⌋=∑i=0n⌊ai+b%cc⌋+⌊bc⌋(n+1){b}\geq{c}\Rightarrow\sum_{i=0}^n\lfloor \frac{ai+b}{c}\rfloor=\sum_{i=0}^n\lfloor \frac{a i+b\% c}{c}\rfloor+\lfloor\frac{b}{c}\rfloor(n+1)

因此

a≥c∣∣b≥c⇒∑i=0n⌊ai+bc⌋=∑i=0n⌊(a%c)i+b%cc⌋+⌊bc⌋(n+1)+⌊ac⌋n×(n+1)2{a}\geq{c}||{b}\geq{c}\Rightarrow\sum_{i=0}^n\lfloor \frac{ai+b}{c}\rfloor=\sum_{i=0}^n\lfloor \frac{(a\%c) i+b\% c}{c}\rfloor+\lfloor\frac{b}{c}\rfloor(n+1)+\lfloor\frac{a}{c}\rfloor\frac{n\times (n+1)}{2}

⇒F(a,b,c,n)=F(a%c,b%c,c,n)++⌊bc⌋(n+1)+⌊ac⌋n×(n+1)2\Rightarrow F(a,b,c,n) = F(a\%c,b\%c,c,n)++\lfloor\frac{b}{c}\rfloor(n+1)+\lfloor\frac{a}{c}\rfloor\frac{n\times (n+1)}{2}

之后只要解决a<c&&b<ca \lt c \&\& b\lt c的情况就好了（？

由

∑i=0n⌊ai+bc⌋=∑i=0n∑j=1⌊ai+bc⌋1=∑i=0n∑j=1⌊an+bc⌋[j≤⌊ai+bc⌋]\sum_{i=0}^n\lfloor \frac{ai+b}{c}\rfloor =\sum_{i=0}^n\sum_{j=1}^{\lfloor \frac{ai+b}{c}\rfloor}1 =\sum_{i=0}^n\sum_{j=1}^{\lfloor \frac{an+b}{c}\rfloor}[{j\leq \lfloor \frac{ai+b}{c}\rfloor}]

交换求和顺序（

⇒∑j=1⌊an+bc⌋∑i=0n[j≤⌊ai+bc⌋]\Rightarrow \sum_{j=1}^{\lfloor \frac{an+b}{c}\rfloor}\sum_{i=0}^n[{j\leq \lfloor \frac{ai+b}{c}\rfloor}]

又有

⌊ab⌋≥c⇔a≥bc\lfloor \frac{a}{b} \rfloor \geq c \Leftrightarrow a\geq bc

⌈ab⌉≤c⇔a≤bc\lceil \frac{a}{b} \rceil \leq c \Leftrightarrow a\leq bc

因此

=∑j=1⌊an+bc⌋∑i=0n[jc≤ai+b]=∑j=1⌊an+bc⌋∑i=0n[⌈jc−ba⌉≤i]=∑j=1⌊an+bc⌋[n+1−⌈jc−ba⌉]=\sum_{j=1}^{\lfloor \frac{an+b}{c}\rfloor}\sum_{i=0}^n[jc\leq {ai+b}] =\sum_{j=1}^{\lfloor \frac{an+b}{c}\rfloor}\sum_{i=0}^n[\lceil \frac{jc-b}{a} \rceil \leq i] =\sum_{j=1}^{\lfloor \frac{an+b}{c}\rfloor}[n+1-\lceil \frac{jc-b}{a} \rceil]

=∑j=1⌊an+bc⌋[n+1−⌊jc−b+a−1a⌋]=\sum_{j=1}^{\lfloor \frac{an+b}{c}\rfloor}[n+1-\lfloor \frac{jc-b+a-1}{a} \rfloor]

=n⌊an+bc⌋−∑j=1⌊an+bc⌋[⌊jc−b+a−1a⌋−1]=n⌊an+bc⌋−∑j=0⌊an+bc⌋−1[⌊(j+1)c−b−1a⌋]=n\lfloor \frac{an+b}{c}\rfloor-\sum_{j=1}^{\lfloor \frac{an+b}{c}\rfloor}[\lfloor \frac{jc-b+a-1}{a} \rfloor-1] =n\lfloor \frac{an+b}{c}\rfloor-\sum_{j=0}^{\lfloor \frac{an+b}{c}\rfloor-1}[\lfloor \frac{(j+1)c-b-1}{a} \rfloor]

因此我们有a,b<ca,b\lt c时

F(a,b,c,n)=n⌊an+bc⌋−F(c,−1−b+c,a,⌊an+bc⌋−1)F(a,b,c,n)=n\lfloor \frac{an+b}{c}\rfloor-F(c,-1-b+c,a,\lfloor \frac{an+b}{c}\rfloor-1)

然后就 可以递归了 终止条件a=0

以下代码

1
2
3
4
5
6
ll exgcd(ll a, ll b, ll c, ll n){
      if(a==0) return (n+1)*(b/c);
      if(a>=c||b>=c) return exgcd(a%c, b%c, c, n) + floor(a/c)*n*(n+1)/2 + floor(b/c)*(n+1);
      ll temp = (a*n+b)/c;
      return n*temp - exgcd(c, c-b-1, a, temp-1);
}
数论