CSP-J 2019 第一轮 第 10 题：求最大公约数

题目

$319$ 和 $377$ 的最大公约数是（）。

选项

• A. 27
• B. 33
• C. 29
• D. 31

答案

C

题解

选 C. 29。

用辗转相除法： \[ 377=319\times1+58 \] \[ 319=58\times5+29 \] \[ 58=29\times2+0 \]

最后一个非零余数是 29，所以最大公约数是 29。