type
status
date
slug
summary
tags
category
icon
password

介绍

欧几里德算法,又叫做辗转相除法,用于计算两个正整数a,b的最大公约数(the greatest common divisor)。

计算公式

证明

第一步:不妨假设 ,则 ,其中
第二步:取 ,其中,易得 也是 的因子
第三步:而,即 c 也是 a mod b 的一个因子
从而,结论得证

代码

C++版本

除此之外,还可以用递归来定义此函数

python版本

  1. 使用math库中带的gcd函数
  1. 手写GCD
 
拓展欧几里得算法贪心算法
Serendipity
Serendipity
From CCNU
Announcement
type
status
date
slug
summary
tags
category
icon
password
本网站部署于国外服务器,国内访问较慢。多刷新或挂梯子。