[关闭]
@samzhang 2017-04-18T10:59:41.000000Z 字数 786 阅读 14162

Exgcd

数论


//下面假设都是非负整数

我们想求得一组使得

根据

如果我们现在有使得

那么我们可以钦定

注意到


其中表示小于等于的最大整数。

所以

注:我们注意到这个方程里面有个未知数却只有个方程,那么根据线性代数相关知识我们可以知道这东西是有无数组解的。
注意到这个等式每一项只与a或b有关,所以我们只需要按照a和b分类一下这个东西就可以获得一组特解

魔改开始!

魔改结束!

看这个东西长得这么漂亮,这么对称,显然我们可以得到一组特解

聪明的你一定发现了这个东西是个递归的式子,那么我们肯定要找到那组base case(也就是递归基). 聪明的你也一定发现了这里的递归基就是当

时我们想求使得的话,显然就可以啦,大功告成。

附一下代码:

  1. pair<int,int> exgcd(int a,int b){
  2. if(b == 0)return make_pair(1,0);
  3. pair<int,int>temp = exgcd(b,a%b);
  4. pair<int,int>ans = make_pair(temp.second,temp.first-a/b*temp.second);
  5. return ans;
  6. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注