解题思路

使用辗转相除法：把较大的数除以较小的数，接着用除数和余数继续计算，直到余数为0，最后的除数就是最大公约数。

参考代码

// 读取题目给出的数据。
// 按照题意完成计算。
// 输出最终答案。
#include <iostream>
using namespace std;
int main(){
long long m,n;
cin>>m>>n;
while(n){
long long t=m%n;
m=n;
n=t;
}
cout<<m;
}

复杂度

时间复杂度O(log N)，空间复杂度O(1)。