NOIP2012拓展欧几里得

时间:2023-03-08 18:57:46
NOIP2012拓展欧几里得

拉板题,,,不说话

我之前是不是说过数据结构很烦,,,我想收回,,,今天开始的数论还要恶心,一早上听得头都晕了

先来一发欧几里得拓展裸

 #include <cstdio>
void gcd(int a,int b,int&d,int&x,int&y)
{
if(!b)d=a,x=,y=;
else gcd(b,a%b,d,y,x),y-=x*(a/b);
}
int main()
{
int a,b,d,x,y;
scanf("%d%d",&a,&b);
gcd(a,b,d,x,y);
x=(x%b+b)%b;
printf("%d\n",x);
return ;
}

代码又短又好懂,所以就不解释了

可以看出gcd中所有关于xy的东西删光就变成了朴素的球最大公约数的gcd——其实本程序中的欧几里得是拓展欧几里得,所以应该叫exgcd而不是gcd,但是不需要求gcd所以就偷个懒好了

然后通过数学推导就能发现每一次辗转相除对应的x y的变化规律

然后就没有然后了

——虽然听晕了,但是能15行解决题目的感觉真爽