CloudLunar
主页
知识库
人文社科
自然科学
跨学科领域
热门分类
算法及题库
云璟月's
墨色集(设计)
指尖集(代码)
未央集(随笔)
流觞集(语录)
如花集(书影)
纸鸢集(小说)
登录
B站
微博
人人
开心
Twitter
Facebook
RSS订阅链接
留言板
关于我
在社交网站上关注我
B站
微博
人人
开心
Twitter
Facebook
RSS订阅
RSS订阅链接
留言板
关于我
查看CodeVS/1212的源代码
←
CodeVS/1212
因为以下原因,你没有权限编辑本页:
你刚才请求的操作只对属于该用户组的用户开放:
用户
您可以查看并复制此页面的源代码:
[[分类:简单数学问题]] {{信息题|最大公约数|http://www.wikioi.com/problem/1212/|1|100}} ==题意== 求最大公约数。 ==题解== 第一反应是枚举2~根号n,然后悲催的发现2^31-1。 然后悠悠地想起来还有更相减损术和辗转相除法这一说,必修三都忘光了- - 欸……高考前数学老师还特意复习了来着的。挖个地洞钻进去。 凭着模糊的印象写了下居然AC了。嗯是这样的: <pre> int gcd(int a,int b){//要求a>b if(a%b==0)return b; return gcd(b,a%b); }</pre> 大概原理是,如果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代码已折叠 |<pre> #include<cstdio> #define max(a,b) (((a)>(b))?(a):(b)) #define min(a,b) (((a)<(b))?(a):(b)) int gcd(int a,int b){ if(a%b==0)return b; return gcd(b,a%b); } int main(){ int a,b; scanf("%d%d",&a,&b); printf("%d",gcd(max(a,b),min(a,b))); return 0; } </pre> |code1212}}
该页面使用的模板:
模板:信息题
(
查看源代码
)
模板:折叠
(
查看源代码
)
返回
CodeVS/1212
。
著作权声明
[
编辑
]
除非另有说明,本
网站内容
采用
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议
进行许可(中国大陆可以参照
知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议
,如有不同以前者为准)。
如果需要商业化使用,请另联系作者取得授权。
关于
[
编辑
]
联系
@云璟月Lunar
的新浪微博
本站RSS:
RSS链接