1035: 【例】【入门】求两个自然数M和N的最大公约数

内存限制：16 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：41 解决：24

题目描述

求两个自然数M和N的最大公约数(M，N都在长整型范围内）

（5.1.42）

输入

输入一行，包括两个整数.

输出

输出只有一行（这意味着末尾有一个回车符号），包括1个整数。

样例输入 复制 

45 60

样例输出 复制 

15

提示

朴素法： 

#include <iostream>
#include <iomanip>
using namespace std;
int main(){
    long long  m,n,i;
    cin>>m>>n;
    for(i=min(m,n);i>=1;i--){
    	if(m%i==0&&n%i==0){
    		cout<<i<<endl;
    		break;
		}
	}
}

辗转相除法（while循环）： 

#include<bits/stdc++.h>
using namespace std;
long long m,n,r;
int main()
{
    cin>>m>>n;
    r=m%n;
    while(r!=0) {
    	m=n;
    	n=r;
    	r=m%n;
	}
	cout<<n<<endl;
	return 0;
}

辗转相除法（递归）： 

#include<bits/stdc++.h>
using namespace std;
long long gcd(long long x,long long y) {
	if (y==0) return x;
	else return gcd(y,x%y);
}
int main(){
    long long m,n;
    cin>>m>>n;
    cout<<gcd(m,n);
	return 0;
}

内置函数： 

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long m,n;
    cin>>m>>n;
    cout<<__gcd(m,n);
	return 0;
}


来源/分类

提交提交记录统计露一手!