#include<iostream> #include<algorithm> usingnamespace std; int a,b; int gcd(int a,int b) {if(a%b==0) return b;elsereturn gcd(b,a%b); } int main() {while(cin>>a>>b){if(a<b) swap(a,b);cout<<gcd(a,b)<<endl;} } 原文：http://www.cnblogs.com/OZTOET/p/5165774.html
一、最大公约数和最小公约数的关系假设x和y的最大公约数是m,最小公倍数是n,则xy=mn(所以我们只需求出两个数的最大公约数，即可得到它们的最小公倍数)二、最大公约数的三种求法1.更相止损法 ?? 两个正整数a和b(a>b)，它们的最大公约数等于a-b的差值c和较小数b的最大公约数。我来介绍一下这个算法的优点，就是避免了大整数取模导致效率低下，但是运算次数要比辗转相除多得多，所以我们在使用的时候需要判断一下。int gcd(int a,int b...
辗转相除法求最大公约数 int main() {unsigned int num1, num2, tmp;scanf("%u %u", &num1, &num2);if (num1 < num2) {tmp = num1;num1 = num2;num2 = tmp; //确保num1大于等于num2} while (num2 != 0) {tmp = num1 % num2; //求余数num1 = num2;num2 = tmp; //辗转相除法}printf("最大公约数 = [%u]\n", num1);return 0; }
题目: 见https://www.luogu.com.cn/problem/P1029 思路: 就考了一个最大公因数和最小公倍数的性质以及用欧几里得法求最大公因数,见书P142,然后暴力就完事了 代码: #include<iostream> using namespace std; int x,y,ans; int gcd(int a,int b) {return b?gcd(b,a%b):a; } int main() {cin>>x>>y;for(int i=x;i<=y;i+=x)for(int j=x;j<=y;j+=x){if(i*j==x*y&&gcd(i,j)==x){ans++;}else if(i*j>x*y)//不加这个肯定超时break;}cout<<a...
中M2021春C、Java入门练习第I段——变量、表达式、分支、循环 7-26 最大公约数和最小公倍数 (15 分) 本题要求两个给定正整数的最大公约数和最小公倍数。 输入格式: 输入在一行中给出两个正整数M和N（≤1000）。 输出格式: 在一行中顺序输出M和N的最大公约数和最小公倍数，两数字间以1空格分隔。 输入样例: 511 292 输出样例: 73 2044 鸣谢安阳师范学院段晓云老师和软件工程五班李富龙同学补充测试数据！ 代码： #include <stdio.h>...