真TMD难啊!!!!我真的想*欧几里得
好吧难还是得学啊。。。9九月就初赛
①欧几里得算法
这东西很简单啊。。就记个结论就可以了
然后就没有了
②欧几里得算法的应用
这东西就是用来求最大公约数的
1 2 3 4
| int gcd(int a,int b) { return b?gcd(b,a%b):a; }
|
接下来的才是难点
③欧几里得算法拓展
欧几里得算法拓展用于求
ax+by=gcd(a,b)
的其中一组解
具体过程如下:
ax1+by1=gcd(a,b)
利用欧几里得公式
=>bx2+(a%b)y2=gcd(b,a%b)
可以重复利用欧几里得公式,到最后一层b会变成0
=>(…)xi+(…)yi =gcd(…,0)
最终b变成0时,最后一层的x与y可以求出来
axi+byi=gcd(a,0)=a ∴xi=1,yi=0
现在看上下层的回溯关系
a%b=a−[ba]×b
但是第一步先要利用上面这个公式
ax1+by1=bx2+(a%b)y2
=bx2+(a−[ba]×b)y2
=ay2+bx2−[ba]×b×y2
=ay2+b(x2−[ba]×y2)
所以上下层的x与y的关系:
xi=yi+1yi=xi+1−[ba]×yi+1
之后一层一层回退,求出x1与y1就是最终结果
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| void exgcd(int a,int b) { if(b==0) { x=1; y=0; return; } exgcd(b,a%b); k=x; x=y; y=k-a/b*y; return; }
|
④欧几里得算法拓展的应用
欧几里得还可以求解下面的这种式子或者逆元也可以(逆元我实在不会啊)
ax+by=m
首先要判断这种式子有没有解
所以我们要介绍一下贝祖定理:
1
| 如果a、b是整数,那么一定存在整数x、y使得ax+by=gcd(a,b)。
|
换句话说,如果ax+by=m有解,那么m一定是gcd(a,b)的若干倍。
有一个直接的应用就是 如果ax+by=1有解,那么gcd(a,b)=1(所以欧几里得还可以用来求满足 ax mod b = 1 的最小正整数 x)
反正就是如果那个式子有解,把a与b同时乘k倍,使得gcd(ak,bk)=m
再用之前的方法求解就可以了(指求一组解,不可能求出所有解的)