题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
---|---|---|---|---|---|
最大公约数 | ★☆☆☆☆ | 答案正确 | 100 | 2014/08/16 23:31:13 | 无 |
求最大公约数。
第一反应是枚举2~根号n,然后悲催的发现2^31-1。
然后悠悠地想起来还有更相减损术和辗转相除法这一说,必修三都忘光了- -
欸……高考前数学老师还特意复习了来着的。挖个地洞钻进去。
凭着模糊的印象写了下居然AC了。嗯是这样的:
- int gcd(int a,int b){//要求a>b
- if(a%b==0)return b;
- return gcd(b,a%b);
- }
大概原理是,如果u|a且u|b那么u|(a%b),直到b|a为止,那么b就是所求。
换句话说,如果u|a且u|b,假设a可以分成m份的u,b可以分成n份的u,a%b就是a去除好多倍的n份的u,剩下的一定还是好多份的u,就是u|(a%b)。
然后gcd(a,b)等价于gcd(b,a%b),然后gcd的东西就越来越小。
直到最后b只有一份的u了,那么这就是所求解了。
反正古人很神奇,数论很神奇。
1212.cpp代码已折叠
展开折叠内容
|
---|
显示/移除行号
|