数论--最大公约数和最小公倍数
关注
分享
扫一扫
淼润淽涵
这个作者很懒，什么都没留下…
展开
-
求最大公约数和最小公倍数算法
一、求最大公约数：欧几里德算法欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数其计算原理依赖于下面的定理：定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数缩写为gcd。gcd(a, b) = gcd(b, a mod b)（前提条件是假设a > b 且 r = a mod b, r 不为0）c++代码：//两个...原创 2019-08-21 14:42:34 · 253 阅读 · 0 评论 -
51Nod-1179 最大的最大公约数
Problem Description给出N个正整数，找出N个数两两之间最大公约数的最大值。例如：N = 4，4个数为：9 15 25 16，两两之间最大公约数的最大值是15同25的最大公约数5。Input第1行：一个数N，表示输入正整数的数量。(2<=N<=50000)第2-N+1行：每行1个数，对应输入的正整数.(1<=S[...原创 2019-07-26 16:01:36 · 192 阅读 · 0 评论