Luogu P1082 同余方程(exgcd模版)

传送门

求ax%b = 1,即ax - by = 1;

很明显这是一个exgcd的形式。

那么要做这道题,首先需要gcd和exgcd的算法作铺垫。

gcd(辗转相膜法):

int gcd(int a,int b){
if(b == ){
return a;
}
return gcd(b,a%b);
}

exgcd就是在求出gcd的基础上,求出ax+by = gcd(a,b)的一组x,y的解:

int exgcd(int a,int &x,int b,int &y){
if(b == ){
x = ;
y = ;
return a;
}
int g = exgcd(b,x,a%b,y);
int tx = x;
x = y;
y = tx -a/b*y;
return g;
}

这个算法的原理如下:

  • 当b=0时,gcd(a,b) = a,ax+by 即 a*1 + 0*0 = gcd(a,b);(因为b = 0,y的值其实不重要,这里就写成0)
  • 因为gcd(a,b) =  ax+by,gcd(b,a%b) = ax'+ by',

   每次递归时,gcd(a,b) = gcd(b,a%b),所以ax+by = ax'+ by',

   并且已知 a%b = a-(a/b)*b,那么可以得到

    ax'+by'
= bx + (a%b)y
   = bx + (a-a/b*b)y
   = bx + ay - (a/b)*by
   = ay + b(x-(a/b)*y)
  
    x'=y; y'=(x-(a/b)*y)

有了这些铺垫,再来看这道题:

ax+by=1,即gcd(a,b) = 1,说明a,b一定是互质的,方程才能有解(虽然知道了这个也没什么用orz)。

现在已经求出了一组x,y的解,怎么保证x是最小正整数呢?

已知

   ax+by

  = ax + by + k*ab - k*ab

  = a(x+kb) + (y-ka)b

也就是说,当x改变b的整数倍时,原式的值可以保持不变;

那么最小正整数即为x%b;

但是要考虑x为负数的情况,就要先将x加上b,直到x为正数,再取模,可以得到

  x = (x%b+b)%b;

完整代码如下

#include<cstdio>
using namespace std;
int a,b,x,y;
void exgcd(int a,int &x,int b,int &y){
if(b == ){
x = ;
y = ;
return;
}
exgcd(b,x,a%b,y);
int k = x;
x = y;
y = k-a/b*y;
return;
}
int main(){
scanf("%d%d",&a,&b);
exgcd(a,x,b,y);
x = (x%b+b)%b;
printf("%d",x);
return ;
}
上一篇:shell中使用echo输出时如何指定颜色


下一篇:python数据结构与算法之单链表