【poj 2891】Strange Way to Express Integers（数论--拓展欧几里德求解同余方程组模版题）

题意：Elina看一本刘汝佳的书(O_O*)，里面介绍了一种奇怪的方法表示一个非负整数 m 。也就是有 k 对 ( ai , ri ) 可以这样表示——m%ai=ri。问 m 的最小值。

解法：拓展欧几里德求解同余方程组的最小非负整数解。（感觉挺不容易的......+_+@）

先看前2个关系式：                   m%a1=r1 和 m%a2=r2 →
                                      m-a1*x=r1 和 m-a2*y=r2 →
                                        m=a1*x+r1 和 m=a2*y+r2
                                    a1*x-a2*y=r2-r1 →
     于是用拓展欧几里德求得一个满足这2个关系式/方程联立的最小非负整数解 (x',y')。
那么存在一个：                m'-a1*x'=r1 和 m'-a2*y'=r2 →
                                  m'=a1*x'+r1=a2*y'+r2 →
                                m' %a1=m%a1 和 m' %a2=m%a2 →
                                m' %lcm(a1,a2)=m%lcm(a1,a2) →
                                          m=m'+k*lcm(a1,a2) →
                                  m=(a1*x'+r1)+lcm(a1,a2)*k →
                                  m=      r'       +         a'    *x →
                                      ......
                                      m=ak*y'+rk+lcm(ak-1,ak)*k →
                                而又 m=ak*y'+rk ， r'=ak*y'+rk
                                所以 m=r'
       接着继续将这个式子与 m=a3*y+r3 联立，同样地得到一个新的方程，再一直继续联立下去，由于 x 保证了尽量下，最后的 r' 就是尽量小的答案。

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<iostream>

 5 using namespace std;

 6 typedef long long LL;

 7

 8 LL mabs(LL x) {return x>0?x:-x;}

 9 LL exgcd(LL a,LL b,LL& x,LL& y)

10 {

11     if (!b) {x=1,y=0; return a;}

12     LL d,tx,ty;

13     d=exgcd(b,a%b,tx,ty);

14     x=ty,y=tx-(a/b)*ty;

15     return d;

16 }

17 int main()

18 {

19     LL k;

20     while (scanf("%I64d",&k)!=EOF)

21     {

22       LL aa,rr,a,r; bool ok=false;

23       for (LL i=1;i<=k;i++)

24       {

25         scanf("%I64d%I64d",&aa,&rr);

26         if (ok) continue;

27         if (i==1) a=aa,r=rr;

28         else

29         {//求解同余方程

30           LL d,x,y,t;

31           d=exgcd(a,aa,x,y);//ax-aay=rr-r 有无正负号没有关系

32           if ((rr-r)%d!=0) {ok=true;continue;}//break;} 多组数据要读入完！

33           x=x*((rr-r)/d);//1个解

34           t=mabs(aa/d);//mabs

35           x=(x%t+t)%t;//最小非负整数解

36

37           r=a*x+r,a=a*aa/d;//a=lcm(a,aa)=a*aa/gcd(a,aa)=a*aa/d;

38         }

39       }

40       if (!ok) printf("%I64d\n",r);

41       else printf("-1\n");

42     }

43     return 0;

44 }

巴特西

【poj 2891】Strange Way to Express Integers（数论--拓展欧几里德求解同余方程组模版题）

最新文章

热门文章

巴特西

【poj 2891】Strange Way to Express Integers（数论--拓展欧几里德 求解同余方程组 模版题）

最新文章

热门文章

【poj 2891】Strange Way to Express Integers（数论--拓展欧几里德求解同余方程组模版题）