4fd800b3a8 2011-02-23        kinaba: LL gcd(LL a, LL b)
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	while(a)
4fd800b3a8 2011-02-23        kinaba: 		swap(a, b%=a);
4fd800b3a8 2011-02-23        kinaba: 	return b;
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: LL lcm(LL a, LL b)
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	return a/gcd(a,b)*b;
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: // Assumption: (a/b)*b+(a%b) == a
4fd800b3a8 2011-02-23        kinaba: //   For typical C/C++ compilers, % on negatives satisfies this.
4fd800b3a8 2011-02-23        kinaba: //   To be sure, replace a%b by a-a/b*b
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: LL xgcd(LL a, LL b, LL* x, LL* y) // ax+by=g
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	if(b) {
4fd800b3a8 2011-02-23        kinaba: 		LL yy, g = xgcd(b,a%b,&yy,x);
4fd800b3a8 2011-02-23        kinaba: 		*y = yy - a/b**x;
4fd800b3a8 2011-02-23        kinaba: 		return g;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 	else {
4fd800b3a8 2011-02-23        kinaba: 		*x=1, *y=0;
4fd800b3a8 2011-02-23        kinaba: 		return a;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: }