关键词：

40-公约数和公倍数

内存限制:64MB 时间限制:1000ms Special Judge: No
accepted:30 submit:47

第一行输入一个整数n（0<n<=10000)，表示有n组测试数据;
随后的n行输入两个整数i,j（0<i,j<=32767)。

输出每组测试数据的最大公约数和最小公倍数

3
6 6
12 11
33 22

6 6
1 132
11 66

分析：
　　①、求最大公约数可以用递归的方法（gcd）；
　　

1 int gcd(int a, int b)
2 
3     if(b == 0) return a;
4     return gcd(b, a%b);
5 

C/C++代码实现（AC）：
　　

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <stack>
 7 #include <map>
 8 #include <queue>
 9 #include <set>
10 
11 using namespace std;
12 const int MAXN = 510;
13 
14 int gcd(int x, int y)
15 
16     if(y == 0) return x;
17     return gcd(y, x%y);
18 
19 
20 int main()
21 
22 
23     int t;
24     scanf("%d", &t);
25     while(t --)
26     
27         int a, b, temp;
28         scanf("%d%d", &a, &b);
29         temp = gcd(a, b);
30         printf("%d %d\n", temp, a*b/temp);
31     
32 
33     return 0;
34 

acm数论之旅3---最大公约数gcd和最小公倍数lcm(代码片段)

gcd(a,b)，就是求a和b的最大公约数lcm(a,b)，就是求a和b的最小公倍数然后有个公式a*b=gcd*lcm  (gcd就是gcd(a,b)， ( ????? ) 简写你懂吗)lcm(S/a,S/b)=S/gcd(a,b)S=9，a=4，b=6，小数不会lcm，只好保留分数形式去通分约分。LLgc... 查看详情

c_cpplcm，最小公倍数，gcd，最大公约数(代码片段)

查看详情

求两个数的最大公约数和最小公倍数(代码片段)

求最大公约数利用辗转相除法：longlonggcd(longlonga,longlongb)if(b==0)returna;elsereturngcd(b,a%b); 求最小公倍数时，利用两数的乘积除以这两个数的最大公约数即可：longlonglcm(longlonga,longlongb)longlongtmp=a*b;tmp=tmp/gcd(a,b);returntmp;完整 查看详情

数论代码整理(代码片段)

数论模板此处均为代码，学习出门右转一、公约数、公倍数GCDintgcd(intx,inty)return!y?x:gcd(y,x%y);LCMintlcm(intx,inty)returnx/gcd(x,y)*y;拓展欧几里得intx,y;intex_gcd(inta,intb)if(!b)x=1,y=0;returna;inttemp=ex_gcd(b,a%b);x=y,y=tem 查看详情

最大公约数（gcd）还有最小公倍数（lcm）的共通之处(代码片段)

gcd：intgcd(inta,intb)if(a%b==0)returnb;returngcd(b,a%b); lcm：intgcd(inta,intb)if(a%b==0)returnb;returngcd(b,a%b);intlcm(inta,intb)return(a*b)/(gcd(a,b));intmain()inta,b;cin>>a>>b;cout<<lcm(a,b);return0; 总结：事实上，求两个数lcm的本质也还是要用上... 查看详情

数论--最大公约数gcd和最小公倍数lcm

记gcd(a,b)为a,b的最大公约数记lcm(a,b)为a,b的最小公倍数可知lcm=a*b/gcd,由于a*b可能过大，我们写成lcm=a/gcd*b 辗转相除法求gcd递归写法：1longlonggcd(longlonga,longlongb)2{3returnb?gcd(b,a%b):a;4} 几个小公式：gcd(ka,kb)=k*gcd(a,b)lcm(ka,kb)= 查看详情

最大公约数和最小公倍数——递归与非递归（王道）(代码片段)

最大公约数：递归：#include<iostream>usingnamespacestd;intgcd(inta,intb)if(b==0)returna;elsereturngcd(b,a%b);//b和a除以b的余数计算最大公约数intmain()inta,b;cin>>a;cin>>b;cout<<gcd(a,b)<<endl 查看详情

数论----gcd和lcm(代码片段)

gcd即最大公约数，lcm即最小公倍数。首先给出a×b=gcd×lcm证明：令gcd(a,b)=k,a=xk,b=yk,则a×b=x*y*k*k，而lcm=x*y*k，所以a*b=gcd*lcm。所以求lcm可以先求gcd，而求gcd的方法就是辗转相除法，也叫做欧几里德算法，核心为gcd(m,n)=gcd(n,... 查看详情

求gcd和lcm，即指求最大公约数和最小公倍数。

求GCD和LCM，即指求最大公约数和最小公倍数。写两个函数，分别求两个整数的最大公约数和最小公倍数，用主函数调用这两个函数并输出结果。两个整数在主函数中从键盘输入。输入每行输入2个正整数。若输入的2个整数中任何... 查看详情

c语言编程

整数a,b的最大公约数是指既能被a整除又能被b整除的最大整数。整数a,b的最小公倍数是指既是a的倍数又是b的倍数的最小整数。编写两个函数，一个函数gcd()的功能是求两个整数的最大公约数，另一个函数mul()的功能是求两个整数... 查看详情

最大公约数(代码片段)

两个数x，y的最大公约数记为gcd（x，y）两个数x，y的最小公倍数记为lcm（x，y）则有：gcd（x，y）*lcm（x，y）=x*y求解最大公约数的方法：1、辗转相减法:(又称更相减损术)当求大数的最大公约数时，以较大的数减去减小的数，接着... 查看详情

公约公倍数(代码片段)

问题描述输入两个正整数，求其最大公约数和最小公倍数。输入格式每行输入两个正整数a,b(1≤a,b≤104)，空格隔开。输出格式输出两行，分别是a,b的最大公约数和最小公倍数。代码packagejavaexam;importjava.util.Scanner;publicclassCommonDMpub... 查看详情

[haoi2018]奇怪的背包（dp，数论）(代码片段)

...办？我们发现每一个物品的贡献其实就是它的重量和P的公约数，而P的约数个数小于3000，我们可以在读入的时候就让它和P取gcd，这样会有很多物品的贡献重复（我们开个桶归类）然后每一次都按P的约数来跑完全背包。（注意要... 查看详情

求gcd（最大公因数）,lcm（最小公倍数）模板(代码片段)

gcd（最大公因数）,lcm（最小公倍数）1#include<iostream>2usingnamespacestd;3intgcd(inta,intb)//辗转相除法（欧几里德算法）求最大公约数45returnb?gcd(b,a%b):a;67intlcm(inta,intb)89returna*b/gcd(a,b);//最小公倍数1011intmain()1213inta 查看详情

luogup1029最大公约数和最小公倍数问题[gcd][数论]

...列条件的P,Q的个数条件:1.P,Q是正整数2.要求P,Q以x0为最大公约数,以y0为最小公倍数.试求:满足条件的所有可能的两个正整数的个数.输入输出格式输入格式：二个正整数x0,y0输出格式：一个数，表示求出满足条件的P,Q的个数输入输出... 查看详情

数论再谈

最大公约数和最小公倍数记$a$和$b$最大公约数为$\\gcd(a,b)$,记$a$和$b$最小公倍数数为$lcm(a,b)$。设$a>b$。求最大公约数$gcd(a,b)=gcd(b,a\\modb)$。证明如果$a$是$b$的倍数， 查看详情

最大公约数和最小公倍数(代码片段)

求数a和数b的最大公约数和最小公倍数.(a和b都是(1--100000)之间的数)输入有多组测试数据．每一组输入的测试数据占一行．从键盘输入a,b．当输入为0和０时程序结束．输出输出最大公约数和最小公倍数．每一组测试数据的输出结... 查看详情

模板：最大公约数（欧几里得）和最小公倍数

1typedeflonglongLL;23LLgcd(LLa,LLb){4return(b==0)?a:gcd(b,a%b);5}67LLlcm(LLa,LLb){8returna/gcd(a,b)*b;9}  查看详情