【c++】分蛋糕（数论）

分蛋糕

题目难度：简单

时间限制：1024ms

内存限制：128mb

题目描述

把一块 m 厘米 * n 厘米的蛋糕分割成同样大的正方形，如果要求没有蛋糕剩余，分割出的正方形蛋糕最大边长是多少厘米？（最少不能少于 1 厘米* 1 厘米）

如：一块 6 厘米 * 4 厘米的蛋糕，能够分割的最大的正方形的边长为 2 厘米。

输入格式

两个整数 m 和 n 。

输出格式

能够分割的最大正方形的边长。

样例数据

输入1#

6 4

输出1#

2

提示

对于80%数据，1≤n,m≤10^7，

对于100%数据，1≤n,m≤10^18，

---

思路：

这道题很简单啊,就是求两个数的最大公因数嘛

【数论】最大公因数和最小公倍数-CSDN博客

---

代码：

#include
using namespace std;
int f(long long a,long long b){
	if(b==0){
		return a;
	}
	f(b,a%b);
}
int main(){
	long long a,b;
	cin>>a>>b;
	long long c=f(a,b);
	cout<
	return 0;
}//公因数与公倍数