三体第二部 黑暗森林:写2个函数分别求2个整数的最大公约数和最小公倍数用主函数调用这2个函数，并输出结果，2个整数由键盘输入

#include<iostream>
using namespace std;
int max(int x,int y)
{
int m=x;int n=y;
while(m!=n)
{
if(m>n)
n+=y;
else
m+=x;
}
return m;
}

int min(int m,int n)
{
while(m!=n)
{
if(m>n)
m-=n;
else
n-=m;
}
return m;
}

void main()
{
int x,y;
cin>>x>>y;
cout<<max(x,y)<<endl;
cout<<min(x,y)<<endl;
}
欧几里德算法
欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：

定理：gcd(a,b)=gcd(b,(a mod b))

证明：a可以表示成a=kb+r，则r=(a mod b)
假设d是a,b的一个公约数，则有
d|a,d|b，而r=a-kb，因此d|r
因此d是(b,(a mod b))的公约数

假设d是(b,(a mod b))的公约数，则
d|b,d|r，但是a=kb+r
因此d也是(a,b)的公约数

因此(a,b)和(b,(a mod b))的公约数是一样的，其最大公约数也必然相等，得证

gcd(55,22)=gcd(22,11)=gcd(11,0)=11

用辗转相除法可求最大公约数。求出a、b最大公约数后，最小公倍数有个简单的换算关系：最小公倍数=（a*b）/最大公约数。
下面用gcd表示最大公约数，lcm表示最小公倍数

#include <stdio.h>
int gcd(int m,int n)
{
int t;
while(t=m%n)
{
m=n;
n=t;
}
return n;
}

int lcm(int m, int n)
{
return m*n/gcd(m,n);
}

main()
{
int a,b;
scanf("%d%d",&a,&b);
printf("GCD is %d\n",gcd(a,b));
printf("LCM is %d\n",lcm(a,b));
return 0;
}

main()
{int m,n,gy,gb;
printf("input two number:");
scanf("%d%d",&m,&n);
printf("gy=%d,gb=%d",y(m,n),b(m,n));
getch();
}
y(int m,int n)
{int i;
for(i=m;i>0;i--)
if((m%i==0)&&(n%i==0)) return i;
}
b(int m,int n)
{int i;
i=m;
while(!((i%m==0)&&(i%n==0))) i++;
return i;
}

main()
{
int m,n,t,a,b;
scanf("%d,%d",&m,&n);
if(m<n) {t=m;m=n;n=t;}
a=m;b=n;
while(b!=0)
{t=a%b;
a=b;
b=t;}
printf("%d",a);
printf("\n%d",m*n/a);}

#include "stdio.h"
hcf(u,v)
int u,v;
{ int a,b,t,r;
if(u>v)
{t=u;u=v;v=t;}
a=u;b=v;
while((r=b%a)!=0){b=a;a=r;}
return(a);
}
lcd(u,v,h)
int u,v,h;
{
return(u*v/h);
}
main()
{int u,v,h,l;
scanf("%d,%d",&u,&v);
h=hcf(u,v);
printf("H.C.F=%d\n",h);
l=lcd(u,v,h);
printf("L.C.D=%d\n",l);
}