Artifact 9e6d3cbd67078cb94df7fdd01ac6cc161e652c66

• File _lib/numeric/gcd_lcm.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]
• File lib/numeric/gcd_lcm.cpp
  • 2011-02-23 11:18:09 - part of checkin [23dfcca431] on branch trunk - renamed _lib to lib (user: kinaba) [annotate]

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

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

// Assumption: (a/b)*b+(a%b) == a
//   For typical C/C++ compilers, % on negatives satisfies this.
//   To be sure, replace a%b by a-a/b*b

LL xgcd(LL a, LL b, LL* x, LL* y) // ax+by=g
{
	if(b) {
		LL yy, g = xgcd(b,a%b,&yy,x);
		*y = yy - a/b**x;
		return g;
	}
	else {
		*x=1, *y=0;
		return a;
	}
}