原理显然

由于当x,y都为奇数时进行辗转相见

每次减完必有偶数

而偶数最多除log次

那么也最多减log次

复杂度有保证

注：代码未验证

int gcd(int x,int y){

	int res=1;

	while(y){

		if(x%2==0&&y%2==0) res*=2;

		else if(x%2==0) x>>=1;

		else if(y%2==0) y>>=1;

		else{

			if(x>y) swap(x,y);

			y-=x;

		}

	}

	return x*res;

}

最新文章

1. Asp.Net WebApi开发注意
2. android intent和intent action大全
3. MySQL绿色版的安装（mysql-5.6.22-win32.zip）
4. 【Cocos2d-x 3.X 资源及脚本解密】
5. JS 中的 Window 对象
6. Educational Codeforces Round 6 C. Pearls in a Row
7. (转)apache的keepalive和keepalivetimeout（apache优化）
8. [AH/HNOI2017]大佬
9. powershell_基础篇
10. Educational Codeforces Round 53 (Rated for Div. 2)G. Yet Another LCP Problem
11. 解决：angularjs radio默认选中失效问题
12. Android动态添加Device Admin权限
13. 4. Father's Impact on a Child's Language Development 父亲对孩子语言发展的影响
14. MongoDB高级操作(2)
15. [POI2013]Polaryzacja
16. 【原】getInputStream()与getParameterMap()获得Post请求的数据区别
17. gradle多项目构建及依赖
18. CGIC函数说明
19. IEnumerator & IEnumerable
20. 软件包管理yum

热门文章

1. 获取kafka的lag, offset, logsize的shell和python脚本
2. UI Testing in Xcode 7
3. Ubuntu 18.04 下用命令行安装Sublime
4. day3- python 注册
5. 通过composer安装阿里大于接口扩展
6. Python模块(二)(序列化)
7. Gym - 100781A Adjoin the Networks （树的直径）
8. zoj 4057
9. Python中的魔法函数__repr__和__str__的实质性区别
10. splay模板三合一 luogu2042 [NOI2005]维护数列/bzoj1500 [NOI2005]维修数列 | poj3580 SuperMemo | luogu3391 【模板】文艺平衡树（Splay）