pku 2891Strange Way to Express Integers 一元模线性方程组解释

2019-04-13 21:14发布

站内文章 / 模拟电子
14526 0 1505
一元模线性方程组指的是如下形式的方程组：                             x = r1 (mod a1)         x = r2(mod a2)          .......       x = r n(mod an)        对于这类问题的处理方法，是每次合并两个方程，先合并前两个，再将这个方程和第三个合并，......，这样最后就只剩下一个模线性方程，那么要怎么合并呢？  就拿前两个方程为例，我们可以根据模定义得到       x = a1 * y1  + r1①                           x = a2 * y2 + r2 ②       我们先求解出a1 * y1 + r1的一个值k，令m = lcm(a1 , a2)，则前两个方程的合并结果就是 x = k(mod m)，原因何在呢？
      由定理：若a = b (mod m) ，且d | m，则a = b (mod d)       因为 x = k(mod m) ，a1 | m , 所以有x = k(mod a1)，因为k = a1 * y1 + r1 ， 所以x = r1（mod a1）,同理可得x = r2（mod a2），证明结束。
     然后，剩下的问题就是怎么求出k了，求k只要求出y1，然后代入a1 * y1 + r1即可。      根据①②，a1 * y1 + r1 = a2 * y2 + r2，移项a1 * y1 = r2  -  r1 + a2 * y2，取模得到a1 * y1 = r2 - r1 (mod a2)，变成求这个方程的一个解，这就是喜闻乐见的求一元模线性方程的问题了，至此y1就能求得了。
下面给出一道求一元模线性方程组的例题 ， pku2891 /* 题目描述：给出n个ai,ri，求满足所有x=ri（ai）的最小的x */ #pragma warning(disable:4786) #pragma comment(linker, "/STACK:102400000,102400000") #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i) #define mem(a,x) memset(a,x,sizeof(a)) #define lson l,m,x<<1 #define rson m+1,r,x<<1|1 using namespace std; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; const double PI = acos(-1.0); const double eps=1e-8; int n; LL ex_gcd(LL a , LL b , LL &x ,LL &y) { if(b==0){ x = 1 ; y = 0; return a; } LL d = ex_gcd(b , a%b , y , x); y = y - a / b * x; return d; } LL solve() { LL a1 , r1 , a2 , r2 , x0 , y0; bool ok = 1; scanf("%lld%lld",&a1 , &r1); for(int i = 1 ; i< n ; i++){ scanf("%lld%lld",&a2 , &r2); LL d = ex_gcd(a1 , a2 , x0 , y0); LL c = r2 - r1; if(c % d){ ok = 0; } LL m= a2 / d; x0 = (x0 * c / d % m + m)%m; r1 = a1 * x0 + r1; a1 = a1 * (a2 / d); } if(!ok) return -1; else return r1; } int main() { while(scanf("%d",&n)!=EOF){ LL ans = solve(); printf("%lld ",ans); } return 0; }

热门文章