本文共 634 字,大约阅读时间需要 2 分钟。
例如:求a, b的最大公约数即gcd(a, b) 当b != 0时, b = a%b, a = b,继续gcd(a, b) 当b == 0时,此时的a就是a,b的最大公约数
int gcd(int a, int b) { return b ? gcd(b, a%b) : a;}
int gcd(int a, int b) { int temp; while (b) { temp = a; a = b; b = temp%b; } return a;}
我们知道,在数学中,对于任意两个正整数a和b,必定存在一对整数s、t使得sa+tb = gcd(a,b)void exgcd(int a, int b, int * s, int * t) { if (b == 0) { *s = 1, *t = 0; }else { int next_s, next_t; exgcd(b, a%b, &next_s, &next_t); *s = next_t, *t = next_s - a/b * next_t; }}
当b == 0时可取s = 1, t = 0; 当b != 0时s = next_t, s = next_s - a/b * next_t(即s,t与下一层的s, t存在的关系);
转载地址:http://oweff.baihongyu.com/