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; } }