蓝桥杯 公倍数 大数 更相减损法 最大公约数
为什么1小时有60分钟,而不是100分钟呢?这是历史上的习惯导致。 但也并非纯粹的偶然:60是个优秀的数字,它的因子比较多。 事实上,它是1至6的每个数字的倍数。即1,2,3,4,5,6都是可以除尽60。 我们希望寻找到能除尽1至n的的每个数字的最小整数。 不要小看这个数字,它可能十分大,比如n=100,则该数为: 69720375229712477164533808935312303556800 请编写程序,实现对用户输入的 n (n<100)求出1~n的最小公倍数。 例如: 用户输入: 6 程序输出: 60 用户输入: 10 程序输出: 2520 虽然题目描述的很高端,但实际上就是从1-n这n个数求最小公倍数,算法也很简单,就是先把第一个数和第二个数的最小公倍数求出来,然后再将这个最小公倍数与第三个数求最小公倍数,以此类推,麻烦的地方是数据规模,很明显超过了任何数据类型的范围,但是这道题目如果放到java中,那是so easy,Biginteger分分钟搞定,因为要求最小公倍数,涉及到大数的加减乘除甚至取模运算,极为变态,当然,可以到网上找到相应的大数模板,在此我就不在自己构造大数运算了,而是提供一种比较适合进行大数求最小公倍数/最大公约数的方法:更相减损法,made in china哦。 更相减损法 下面上通过更相减损法设计的本道题目,因为用了long long,所以只有一组数据过不去,如果放到正式比赛,也是可以得分的
#include<iostream> typedef long long ll; using namespace std; void swap(ll &a,ll &b) { if(a<b) { a=a+b; b=a-b; a=a-b; } } int gcd(ll a,ll b) { ll two=1; while(a%2==0&&b%2==0) { a=a/2; b=b/2; two=two*2; } while(1) { swap(a,b); a=a-b; if(a==b) break; } return a*two; } ll lcm(ll a,ll b) { return a*b/gcd(a,b); } int main() { ll n,i,temp; cin>>n; temp=1; for(i=2;i<=n;i++) { temp=lcm(temp,i); } cout<<temp; return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |