Artifact 9e6d3cbd67078cb94df7fdd01ac6cc161e652c66:
0000: 4c 4c 20 67 63 64 28 4c 4c 20 61 2c 20 4c 4c 20 LL gcd(LL a, LL
0010: 62 29 0a 7b 0a 09 77 68 69 6c 65 28 61 29 0a 09 b).{..while(a)..
0020: 09 73 77 61 70 28 61 2c 20 62 25 3d 61 29 3b 0a .swap(a, b%=a);.
0030: 09 72 65 74 75 72 6e 20 62 3b 0a 7d 0a 0a 4c 4c .return b;.}..LL
0040: 20 6c 63 6d 28 4c 4c 20 61 2c 20 4c 4c 20 62 29 lcm(LL a, LL b)
0050: 0a 7b 0a 09 72 65 74 75 72 6e 20 61 2f 67 63 64 .{..return a/gcd
0060: 28 61 2c 62 29 2a 62 3b 0a 7d 0a 0a 2f 2f 20 41 (a,b)*b;.}..// A
0070: 73 73 75 6d 70 74 69 6f 6e 3a 20 28 61 2f 62 29 ssumption: (a/b)
0080: 2a 62 2b 28 61 25 62 29 20 3d 3d 20 61 0a 2f 2f *b+(a%b) == a.//
0090: 20 20 20 46 6f 72 20 74 79 70 69 63 61 6c 20 43 For typical C
00a0: 2f 43 2b 2b 20 63 6f 6d 70 69 6c 65 72 73 2c 20 /C++ compilers,
00b0: 25 20 6f 6e 20 6e 65 67 61 74 69 76 65 73 20 73 % on negatives s
00c0: 61 74 69 73 66 69 65 73 20 74 68 69 73 2e 0a 2f atisfies this../
00d0: 2f 20 20 20 54 6f 20 62 65 20 73 75 72 65 2c 20 / To be sure,
00e0: 72 65 70 6c 61 63 65 20 61 25 62 20 62 79 20 61 replace a%b by a
00f0: 2d 61 2f 62 2a 62 0a 0a 4c 4c 20 78 67 63 64 28 -a/b*b..LL xgcd(
0100: 4c 4c 20 61 2c 20 4c 4c 20 62 2c 20 4c 4c 2a 20 LL a, LL b, LL*
0110: 78 2c 20 4c 4c 2a 20 79 29 20 2f 2f 20 61 78 2b x, LL* y) // ax+
0120: 62 79 3d 67 0a 7b 0a 09 69 66 28 62 29 20 7b 0a by=g.{..if(b) {.
0130: 09 09 4c 4c 20 79 79 2c 20 67 20 3d 20 78 67 63 ..LL yy, g = xgc
0140: 64 28 62 2c 61 25 62 2c 26 79 79 2c 78 29 3b 0a d(b,a%b,&yy,x);.
0150: 09 09 2a 79 20 3d 20 79 79 20 2d 20 61 2f 62 2a ..*y = yy - a/b*
0160: 2a 78 3b 0a 09 09 72 65 74 75 72 6e 20 67 3b 0a *x;...return g;.
0170: 09 7d 0a 09 65 6c 73 65 20 7b 0a 09 09 2a 78 3d .}..else {...*x=
0180: 31 2c 20 2a 79 3d 30 3b 0a 09 09 72 65 74 75 72 1, *y=0;...retur
0190: 6e 20 61 3b 0a 09 7d 0a 7d 0a n a;..}.}.