当前位置: 首页> 财经> 产业 > app开发公司成都_百度刷排名seo软件_西安外包网络推广_如何做营销推广

app开发公司成都_百度刷排名seo软件_西安外包网络推广_如何做营销推广

时间:2025/7/10 17:05:45来源:https://blog.csdn.net/2301_81405396/article/details/146886458 浏览次数:0次
app开发公司成都_百度刷排名seo软件_西安外包网络推广_如何做营销推广

前言

来咯来咯,今天的数论部分来了,今天比较水啊,因为课实在是比较多。

今天的数论部分是讲裴属定理扩展欧几里得算法,当然还有今天的题目(两道树状数组 + 一道连通块的问题)我放到下一篇了。


裴属定理

第一次听到这个定理的时候感觉压力好大,这个名字一看就知道不简单,但是学了之后才发现还挺简单的。

这个裴属定理主要是为了引出后面的扩展欧几里得算法的,所以大家有个印象就好了,不必较真。

话归正题,什么是裴属定理

裴属定理是这样的,对于任意的整数ab,必定存在一组整数xy,使得:

a * x + b * y = gcd(a, b)

老样子,先证明。

我们先证明必定存在一对xy(不一定是整数),使得a * x + b * y = gcd(a, b)

首先设d = gcd(a, b),那么da的约数d也是b的约数。

随后依据算数基本定理将dab展开,可以发现d是包含在ab中的,显然存在一组x, y使得

a * x + b * y = gcd(a, b)

那么如何证明x, y均为整数呢?这个主播是不会的哈,但是主播知道怎么求出xy。使用扩展欧几里得算法


欧几里得算法

在推导扩展欧几里得算法之前呢。我们先来复习一下欧几里得算法


代码

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 = 1y = 任意值,这也就代表着我们要求的x,y可能不止一对,为了方便讨论我们y = 0 啊。

随后我们来分析b不为0的情况。

因为是递归,所以我们假设已知b * y + (a % b)x = gcd(b, a % b)中的xy

我们知道:

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)

到此我们就得出来了xy的递推公式,是不是很简单?


代码

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;
}

关键字:app开发公司成都_百度刷排名seo软件_西安外包网络推广_如何做营销推广

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: