wordpress对外发邮件/国内seo服务商
前言
来咯来咯，今天的数论部分来了，今天比较水啊，因为课实在是比较多。
今天的数论部分是讲裴属定理和扩展欧几里得算法，当然还有今天的题目（两道树状数组 + 一道连通块的问题）我放到下一篇了。
裴属定理
第一次听到这个定理的时候感觉压力好大，这个名字一看就知道不简单，但是学了之后才发现还挺简单的。
这个裴属定理主要是为了引出后面的扩展欧几里得算法的，所以大家有个印象就好了，不必较真。
话归正题，什么是裴属定理？
裴属定理是这样的，对于任意的整数a和b，必定存在一组整数x，y，使得：
a * x + b * y = gcd(a, b)
老样子，先证明。
我们先证明必定存在一对x，y（不一定是整数），使得a * x + b * y = gcd(a, b)
首先设d = gcd(a, b)，那么d是a的约数，d也是b的约数。
随后依据算数基本定理将d和a与b展开，可以发现d是包含在a和b中的，显然存在一组x, y使得
a * x + b * y = gcd(a, b)。
那么如何证明x, y均为整数呢？这个主播是不会的哈，但是主播知道怎么求出x和y。使用扩展欧几里得算法！
欧几里得算法
在推导扩展欧几里得算法之前呢。我们先来复习一下欧几里得算法。
代码
int gcd(int a, int b)
{if(b == 0) return a;return gcd(b, a % b);
}代码很简单对吧，当然思路也很简单，具体推导过程我就不讲了，感兴趣的小伙伴可以去看我前面的博客（数论2）。
扩展欧几里得算法
随后我们来推导扩展欧几里得算法。
首先来分析当b = 0时，x和y的值，设x * a + y * b = a，显然：x = 1，y = 任意值，这也就代表着我们要求的x,y可能不止一对，为了方便讨论我们设y = 0 啊。
随后我们来分析b不为0的情况。
因为是递归，所以我们假设已知b * y + (a % b)x = gcd(b, a % b)中的x和y。
我们知道：
a % b = a - [a/b] * b
设a % b = r
r = a - [a/b] * b
将r代入上式可得：
b * y + (a - [a/b] * b) * x = gcd(b, a % b)
随后我们提出b可得
b * (y - [a/b] * x) + a * x = gcd(b, a % b)
到此我们就得出来了x和y的递推公式，是不是很简单？
代码
int gcd(int a, int b, int& x, int& y)
{if (b == 0){x = 1, y = 0;return a;}int d = gcd(b, a % b, y, x);y -= a / b * x;return d;
}