EXGCD
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=0nai+bc \sum_{i=0}^n\lfloor \frac{ai+b}{c}\rfloor

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

首先有以下公式

ab=a+b1b\lceil \frac{a}{b}\rceil = \lfloor \frac{a+b-1}{b}\rfloor

ab=ab+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=0nai+bcF(a,b,c,n)=\sum_{i=0}^n\lfloor \frac{ai+b}{c}\rfloor

aci=0nai+bc=i=0n(a%c×i+bc+aci)=i=0na%c×i+bc+acn×(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}

bci=0nai+bc=i=0nai+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)

因此

acbci=0nai+bc=i=0n(a%c)i+b%cc+bc(n+1)+acn×(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)+acn×(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=0nai+bc=i=0nj=1ai+bc1=i=0nj=1an+bc[jai+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=1an+bci=0n[jai+bc]\Rightarrow \sum_{j=1}^{\lfloor \frac{an+b}{c}\rfloor}\sum_{i=0}^n[{j\leq \lfloor \frac{ai+b}{c}\rfloor}]

又有

abcabc\lfloor \frac{a}{b} \rfloor \geq c \Leftrightarrow a\geq bc

abcabc\lceil \frac{a}{b} \rceil \leq c \Leftrightarrow a\leq bc

因此

=j=1an+bci=0n[jcai+b]=j=1an+bci=0n[jcbai]=j=1an+bc[n+1jcba]=\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=1an+bc[n+1jcb+a1a]=\sum_{j=1}^{\lfloor \frac{an+b}{c}\rfloor}[n+1-\lfloor \frac{jc-b+a-1}{a} \rfloor]

=nan+bcj=1an+bc[jcb+a1a1]=nan+bcj=0an+bc1[(j+1)cb1a]=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)=nan+bcF(c,1b+c,a,an+bc1)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);
}