ユークリッドアルゴリズムとその拡張ユークリッドアルゴリズム

ユークリッドアルゴリズム(転がり相殺法)の原理(ここをクリック)で解決できます.
コード実現構想:
任意の正の整数a,bに対して,a=kb+r(k,r∈N)a=kb+r(k,rinN)a=kb+r(k,r∈N)r=a%b r=a%b r=a%b
cをa,bの最大公約数とする
c=gcd(a,b)c=gcd(a,b)c=gcd(a,b)¯c∣a,c∣bthereforec|a,c|b¯c∣a,c∣b(c∣a=a c|a=a c∣a=a c∣a=a=a c∣a=a=a c∣a=a=aで整除できるc c)¯r=a=a−k bbecauser=a−kb¯r=a−kb ore c|r∈c∣r∈c=gcd(b,r)therefore c=gcd(b,r)∈c=gcd(b,r)
結論:gcd(a,b)=gcd(b,a%b)gcd(a,b)=gcd(b,a\%b)gcd(a,b)=gcd(b,a%b)
最大公約数(ユークリッドアルゴリズム)
再帰バージョン:

int gcd(int a,int b) {
    return b ? gcd(b, a % b) : a;
}

非再帰(反復)バージョン:

int gcd(int a, int b) {
    while (b) {
        a = a % b;
        swap(a, b);
    }
    return a;
}

ついでに安利の1波は最小の公倍数のコードを求めます
最小公倍数

int lcm(int a, int b) {
    return a / gcd(a, b) * b;  //          
}

ユークリッドアルゴリズムの拡張
簡単に言えば、貝祖等式を解く解(解いたx,yは最小の整数解ではないことに注意)の形である.
a x + b y = g c d ( a , b ) ax + by = gcd(a, b) ax+by=gcd(a,b) a , b ∈ N a, b\in N a,b∈N
証明:
b=0 b=0 b=0の場合、等式はa x+0
すなわちx=1,y=0
a x 1 + b y 1 = g c d ( a , b ) ax_1 + by_1 = gcd(a, b) ax1​+by1​=gcd(a,b) b x 2 + ( a   %   b ) y 2 = g c d ( a , b ) bx_2 + (a\\%\b) y_2=gcd(a,b)bx 2+(a%b)y 2=gcd(a,b)オーラ数得アルゴリズムによれば、gcd(a,b)=gcd(b,a%b)gcd(a,b)=gcd(b,a\%b)gcd(a,b)=gcd(b,a%b)=gcd(a,a%b)¥a x 1+by 1=b x 2+(a%b)y 2therefore ax_1 + by_1 = bx_2 + (a\\%\b) y_2 ∴ax1​+by1​=bx2​+(a % b)y2​ ∵ a   %   b = a − a/b ∗ b\because a\\%\b = a - a/b * b ∵a % b=a−a/b∗b ∴ a x 1 + b y 1 = b x 2 + ( a − a/b ∗ b ) y 2\therefore ax_1 + by_1 = bx_2 + (a - a/b * b) y_2 ∴ax1​+by1​=bx2​+(a−a/b∗b)y2​ ∴ a x 1 + b y 1 = b x 2 + a y 2 − ( a/b ∗ b ) y 2\therefore ax_1 + by_1 = bx_2 + ay_2 - (a/b * b ) y_2 ∴ax1​+by1​=bx2​+ay2​−(a/b∗b)y2​ ∴ a x 1 + b y 1 = a y 2 + b ( x 2 − a/b ∗ y 2 )\therefore ax_1 + by_1 = ay_2 + b(x_2 - a/b * y_2) ∴ax1​+by1​=ay2​+b(x2​−a/b∗y2​)
∴ x 1 = y 2\therefore x_1 = y_2 ∴x1​=y2​ ∴ y 1 = x 2 − a/b ∗ y 2\therefore y_1 = x_2 - a/b * y_2∈y 1=x 2−a/b∗y 2次の手順は直接再帰すればよいコード実装:

int exgcd(int a, int b, int &x, int &y) {
	if (!b) {
		x = 1;
		y = 0;
		return a;
	}
	int tx, ty;
	int res = exgcd(b, a % b, tx, ty);
	x = ty;
	y = tx - a / b * ty;
	return res;
}

簡略版

int exgcd(int a, int b, int &x, int &y) {
	if (!b) {
		x = 1;
		y = 0;
		return a;
	}
	int res = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return res;
}