最大公约数——最小公倍数

#include<algorithm>里面包含库函数

__gcd(a,b);

返回a，b的最大公约数

直接上代码

#include<iostream>
#include<algorithm>
using namespace std;
int GCD(int x,int y)
{return y == 0 ? x : GCD(y,x%y);
}
int gcd(int a,int b)//二进制优化1
{if(b==0)return a;if(a<b)a^=b,b^=a,a^=b;//相当于于swap(x,y);if(a&1){if(b&1)return gcd(a-b,b);elsereturn gcd(a,b>>1);}else{if(b&1)return gcd(a>>1,b);elsereturn gcd(a>>1,b>>1)<<1;}
}
int FASTGCD(int x,int y)//二进制优化2
{int i,j;if(x==0)return y;if(y==0)return x;for(i=0; 0==(x&1); ++i)x>>=1;//除2for(j=0; 0==(y&1); ++j)y>>=1;//除2if(j<i)i=j;while(1){if(x<y)x^=y,y^=x,x^=y;//于swap(x,y);if((x-=y)==0)//产生了x，y的变化return y<<i;while(0==(x&1))x>>=1;}
}
int LCM(int a,int b)
{return a/GCD(a,b)*b;
}
int main()
{int x,y;cin>>x>>y;cout<<GCD(x,y)<<endl;cout<<gcd(x,y)<<endl;cout<<FASTGCD(x,y)<<endl;cout<<LCM(x,y);return 0;
}