§ implementing GCD and LCM

// gcd(x, y) = d <=> min({ ax + by : ax + b y >= 0 })= d
long gcd(long x,long y) { return y == 0 ? x : gcd(y, x%y); }
long lcm(long x,long y) {return x/gcd(x,y)*y;}