最大公约数

最大公约数的求法（辗转相除法）：
判断两个数m,n中n是否是0，有则最大公约数是另外一个数m；否则将m除以n得到余数r，m和n的最大公约数就转化为n和r的最大公约数，递归实现得到结果。

1.递归实现：

int gcd(int x,int y){if(y==0)return x;elsereturn gcd(y,x%y);
}

2.非递归实现

int gcd(int x,int y){while(y){int z=x%y;x=y;y=z;}return x;
}

最小公倍数

最小公倍数实际上就是，两个数的乘积除以最大公约数，所以要求最小公倍数首先要求最大公约数。

计蒜客T1400 最大公约数（二）

#include<iostream>
#include<algorithm>
using namespace std; int yue(int m,int n){
//计算两个非负整数的最大公约数m，n，如果其中一个是0则最大公约数是另外一个
//否则将m除以n得到余数r，m和n的最大公约数即为n和r的最大公约数int max;if(n==0)max=m;elsemax=yue(n,m%n);return max;
}
int main(){int t;cin>>t;while(t--){int m,n;cin>>m>>n;cout<<yue(m,n)<<endl;}return 0;
}

计蒜客T1241 最大公约数与最小公倍数

#include <iostream>
#include <cmath>
using namespace std;
int yue(int m,int n){int max;if(n==0)max=m;elsemax=yue(n,m%n);return max;
}
int main(){int x,y,i,j;cin>>x>>y;int min=x+y,ji=x*y;for(i=x;i<=sqrt(ji);i++){//i的范围可以只找一半范围的，因为只是找最小和j=ji/i;if(ji%i == 0){if(yue(i,j)==x)min=i+j>min ? min :i+j;}}cout<<min;return 0;
}

计蒜客T2112 [NOIP2001]最大公约数和最小公倍数问题

这道题是在平台上几道相关题中难度最高的，要考虑的很多。

1. i的范围只找一半，那cnt计数就要乘以2；
2. 因为是找有多少对，所以(i,j)和(j,i)不一样，但是i=j时cnt要减去一;
3. 最后要注意数的定义范围，用int有几组数据通不过，保险还是用long long吧。

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;ll yue(ll x,ll y){if(y==0)return x;elsereturn yue(y,x%y);
}
int main(){ll x,y,i,j;cin>>x>>y;ll cnt=0,flag=0;ll ji=x*y;ll sq=sqrt(ji);for(i=x;i<=sq;i++){j=x*y/i;ll g=yue(i,j);if(x*y%i==0){if(g==x&&i*j/g==y){cnt++;if(i==sq)flag=1;}}}cnt*=2;if(flag) cnt--;cout<<cnt;return 0;
}