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