[原]NYOJ-公约数和公倍数 -40
//http://acm.nyist.net/JudgeOnline/problem.php?pid=40
公约数和公倍数
时间限制:1000 ms | 内存限制:65535 KB
难度:1
描述
小明被一个问题给难住了,现在需要你帮帮忙。问题是:给出两个正整数,求出它们的最大公约数和最小公倍数。
输入
第一行输入一个整数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来源
[苗栋栋]原创
上传者
苗栋栋
/
*///知识普及
在数学中,辗转相除法,又称欧几里得算法,是求最大公约数的算法。
辗转相除法首次出现于欧几里得的《几何原本》(第VII卷,命题yⅠ和Ⅱ)中,而在中国则可以追溯至东汉出现的《九章算术》。
两个整数的最大公约数是能够同时整除它们的最大的正整数。
辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。
例如,252和105的最大公约数是21(252 = 21 × 12;105 = 21 × 5);因为252 / 105 = 2余42,所以105和42的最大公约数也是21。
在这个过程中,较大的数缩小了,所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时,所剩下的还没有变成零
的数就是两数的最大公约数。由辗转相除法也可以推出,两数的最大公约数可以用两数的整数倍相加来表示,
如21 = 5 × 105 + (?2) × 252。这个重要的等式叫做贝祖等式。
辗转相除法最早出现在欧几里得的几何原本中(大约公元前300年),所以它是现在仍在使用的算法中最早出现的。
这个算法原先只用来处理自然数,但在19世纪,辗转相除法被推广至其他类型的数,如高斯整数和一元多项式。
自此,现代抽象代数概念如欧几里得整环开始出现。后来,辗转相除法又扩展至其他数学领域,如纽结理论和多元多项式。
辗转相除法有很多应用,它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面,
它是RSA算法(一种在电子商务中广泛使用的公钥加密算法)的重要部分。它还被用来解丢番图方程,
寻找满足中国剩余定理的数,或者求有限域的倒数。辗转相除法还可以用来构造连分数,在施图姆定理和
一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。
辗转相除法处理大数时非常高效,它需要的步骤不会超过较小数的位数(十进制下)的五倍。
加百利·拉梅(Gabriel Lamé)于1844年证明了这点,开创了计算复杂性理论
*/
#include<stdio.h>
int main()
{
int a,b,c,n,k;
scanf("%d",&n); //输入一个整数n(0<n<=10000),表示有n组测试数据
while(n--)
{
scanf("%d %d",&a,&b); //输入两个整数 252(=21x12),105(=21x5)或反过来105,252
k = a * b ;
while(b != 0)
{
c = a % b;//c得到是a,b中最小的105,或a除b的余数42(都是那个最大公约数的倍数,例:21)
a=b;
b=c;
}
printf("%d %d\n",a,k/a);
}
return 0;
}
//短除法
#include<stdio.h>
int main()
{
int a,b,gys,gbs,n,t1,t2,i,j;
scanf("%d",&n); //输入一个整数n(0<n<=10000),表示有n组测试数据
for(i=0;i<n;i++)
{
scanf("%d%d",&a,&b); //输入两个整数a,b
t1=(a<b)?a:b;
for(j=t1;j>0;j--) //求最大公约数
{
if(a%j==0&&b%j==0)//一直到从最小的数开始搜索:第一个满足既是a又是b的因子时
{
gys=j;
break;
}
}
t2=(a>b)?a:b;
for(j=t2;j<=a*b;j++) //求最小公倍数
{
if(j%a==0&&j%b==0)//一直到从最大的数开始搜索:第一个满足既是a又是b的倍数的数止。
{
gbs=j;
break;
}
}
printf("%d %d\n",gys,gbs);
}
return 0;
}
最新文章
- ngx_http_fastcgi_module模块.md
- PL/SQL重新编译包无反应
- .NET 二维码生成(ThoughtWorks.QRCode)
- 关于MySQL数据导出导入
- Anychart 破解备注
- //判断是否安装Flash插件
- 自定义一个WPF的PathButton
- Android 百度地图开发之一(Hello BaiDu Map)
- mysql导出数据库几种方法
- 宣布与 NBC 合作直播索契冬季奥运
- js常用随手记
- SHELL脚本学习-练习写一个脚本4
- JS 同步输入
- spring boot 多数据源配置与使用
- Mysql找回丢失密码
- Microsoft translater
- Android学习笔记——从源码看Handler的处理机制
- 基于easyui开发Web版Activiti流程定制器详解(四)——页面结构(下)
- CodeForces1082G Petya and Graph 最小割
- LeetCode: Permutations II 解题报告
热门文章
- Linux进程间通信(三) - 信号
- 贝塞尔曲线与CAShapeLayer的关系以及Stroke动画
- Linux服务器性能日志收集和分析脚本(转)
- memcache 使用方法
- centos7.0 关闭防火墙
- TP框架---thinkphp中ajax分页
- 洛谷P2296 寻找道路==codevs3731 寻找道路
- Android环境搭建 NDK+ADT(免cywgin)
- Java中的String,StringBuilder,StringBuffer三者的区别(转发:https://www.cnblogs.com/su-feng/p/6659064.html)
- python selenium cookie 登录