rt.

学习了二进制 gcd，于是写了这两份代码。

int gcd(int a, int b) {
	int az = __builtin_ctz(a);
	int bz = __builtin_ctz(b);
	int z = az < bz ? az : bz, d;
	b >>= bz;
	while((a >>= az) ^ b) {
		d = b - a;
		az = __builtin_ctz(d);
		if(a < b)b = a, a = d;
		else a = -d;
	}
	return b << z;
}

int gcd(int a, int b) {
	int az = __builtin_ctz(a);
	int bz = __builtin_ctz(b);
	int z = az < bz ? az : bz, d;
	b >>= bz;
	while((a >>= az) ^ b) {
		d = b - a;
		az = __builtin_ctz(d);
		if(a < b)b = a;
		a = d <= 0 ? -d : d;
	}
	return b << z;
}