最大公约和最小公倍数

求最大公约数和最小公倍数的方法

1：可以用整数的因子分解，求最大公约数和最小公倍数，设

    a=p1^r1P2^r2...pk^rk，   b=p1^s1p2^s2....pk^sk，其中p1,p2,...pk是不同的素数，r1,r2,..rk,s1,s2,..sk是非负数，则

  gcd（a,b）=p1^min(r1,s1)p2^min(r2,s2)....pk^min(rk,sk),

  lcm（a,b）=p1^max(r1,s1)p2^max(r2,s2)....pk^max(rk,sk).

2：求最大公约数常用方法是辗转相除法又叫做欧几里德算法

其原理是：设a=qb+r.其中a,b,q,r都是整数,则 gcd(a,b) = gcd(b,r).

 最大公约数函数

int gcd(int a,int b)
{
  if(b==0)
    return a;
  return gcd(b,a%b);
}

最小公倍数函数

int gcd(int a,int b)
{
  if(b==0)
    return a;
  return gcd(b,a%b);
}
int lcm(int x,int y)
{
    return x/gcd(x,y)*y;
}