Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"managingGroups":{},"author":"18fengqianfei","updateTime":1559438560000,"title":"辗转相除 求最大公约数","dislikeCnt":1,"content":"两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。例如,252和105的最大公约数是21(252 \u003d 21 × 12;105 \u003d 21 × 5),因为252 ÷105 \u003d 2......42,所以(105,42)是21。在这个过程中,较大的数缩小了,所以继续进行同样的计算可以不断缩小这两个数直至余数变为零。这时的除数就是所求的两个数的最大公约数。\n\n由辗转相除法也可以推出,两数的最大公约数可以用两数的整数倍相加来表示,如21 \u003d 5 × 105 + (−2) × 252。这个重要的等式叫做贝祖等式(又称“裴蜀定理”)。\n\n 设两数为a、b(a\u003eb),求a和b最大公约数(a,b)的步骤如下:\n\n 用a除以b,得a÷b\u003dq......r1(0≤r1)。\n\n 若r1\u003d0,则(a,b)\u003db;\n\n 若r1≠0,则计算(b,r1),用b除以r1,得b÷r1\u003dq......r2 (0≤r2).\n\n 若r2\u003d0,则(a,b)\u003d\u003d(b,r1)\u003d\u003dr1,\n\n 若r2≠0,则计算(r1,r2),用r1除以r2,得r1÷r2\u003dq......r3 (0≤r3)\n\n\t\t\tint gcd(int a,int b)\n\t\t\t{\n\t\t\t\tif(b\u003d\u003d0)\n\t\t\t\t\t\treturn a;\n\t\t\t\treturn gcd(b,a%b);\n\t\t\t}","threadId":46771,"likeCnt":2,"createTime":1555934515000,"isWorkbook":false,"viewCnt":2201,"openness":1,"fav":false,"id":1062,"trustable":false}