103 条题解

  • 5
    @ 2017-05-07 12:44:41

    /*
    根据题意不难得出 Mt+x-nt-y=pl.即(m-n)t-pl=y-x
    令a=m-n, b=l ,c=y-x ,x=t ,y=-p
    所以本题是求一个不定方程(ax+by=c)的最小非负x
    可以用扩展欧几里德`所谓扩展欧几里得就是我们用欧几里得(a,b)=(b,a MOD b)求最大公约数的同时求出ax+by=(a,b)的一组特解.x0,y0
    令d=(a,b).若c mod d<>0则 Impssible
    否则x0*c/d,y0*c/d为ax+by=c的一组特解
    所以通解为x0*c/d+b/d*t,y0*c/d-a/d*t
    现在剩下的问题就是如何用扩欧求ax+by=(a,b)的一组特解
    方法如下:
    设ax0+by0=(a,b)=(b,a mod b)=bx1+(a mod b)y1 (*)
    而a mod b=a-[a/b]代入(*)式比较系数得x0=y1,y0=x1-y1*[a/b]
    所以我们可以递归实现以上算法.
    最后还要注意几个个细节.
    1.a,b,c若是负数的话.虽然欧几里得MS可以处理.但是mod 运算会变得很别扭.所以为了变成容易实现.建议将a.b.c转换为正数再解.
    对于a我们可以讨论m>n,n<m两种情况.而b本身就是正的.对于c可以加b加到非负为止
    即 ax+by=c 方程两边同时加q倍的b解不变
    2.中间结果有可能超出longint。。最好用int64.虽然NOIP已经不让用了.
    这样这个题就解决了。
    根据同余方程的ax+by=c,可以得出a=n-m,b=l,c=x-y 之后扩展欧几里得求线性同余方程。
    */

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    long long x,y,m,n,l;
    
    void gcd(long long a,long long b,long long& d,long long & x,long long& y)
    {
        if(!b)  {d=a;x=1;y=0;}
        else    {gcd(b,a%b,d,y,x);   y-=x*(a/b);}
    }
    
    int main()
    {
        cin>>x>>y>>m>>n>>l;
        long long a=((n-m)%l+l)%l;  long long b=l;    long long c=((x-y)%l+l)%l;
        long long d;
        gcd(a,b,d,x,y);
        if(c%d)
            cout<<"Impossible"<<endl;
        else
        {
            long long a1=x*(c/d);
            long long a2=abs(l/d);
            while(a1<0)
                a1+=a2;
            while(a1-a2>=0)
                a1-=a2;
            cout<<a1<<endl;
        }
        return 0;
    }
         
    
  • 2
    @ 2019-04-28 18:42:23

    解法拓展欧几里得(exgcd),差不多裸题吧
    有几个坑点:
    1.一定要判断n,m大小并修改a,b的值(具体看代码)
    2.不要忘记有“Impossible”情况
    3.拓展GCD最小整数解问题
    4.本题数据需要longlong
    下面上代码:

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #define LL long long
    using namespace std;
    LL x,y;
    LL s1,s2,m,n,l;
    LL exgcd(LL a,LL b)
    {
        if(b==0) {x=1,y=0;return a;}
        LL t=exgcd(b,a%b);
        LL temp=x; x=y;
        y=temp-a/b*y;
        return t;
    }
    int main()
    {
        cin>>s1>>s2>>m>>n>>l;
        LL a=n-m,b=s1-s2;
        if(a<0) b=-b,a=-a;
        LL ans=exgcd(a,l);
        if(b%ans!=0) cout<<"Impossible"<<endl;
        else cout<<((x*(b/ans))%(l/ans)+(l/ans))%(l/ans);
        return 0;
    }
    
  • 1
    @ 2017-07-20 15:45:32

    青蛙的约会不解释……
    exgcd就可以了(话说这不是模板题吗)

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    #define ll long long
    ll x,y,n,m,L;
    void kzgcd(ll a,ll b,ll &d,ll &x,ll &y)
    {
        if(b==0)
        {
            d=a;x=1;y=0;
            return;
        }
        kzgcd(b,a%b,d,y,x);
        y-=a/b*x;
    }
    int main()
    {
        scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&L);
        ll a=((n-m)%L+L)%L;
        ll b=L;
        ll c=((x-y)%L+L)%L;
        ll d,e,p,q;
        kzgcd(a,b,d,p,q);
        if(c%d)
        {
            printf("Impossible");
            return 0;
        }
        e=b/d;
        printf("%lld",((p*(c/d))%e+e)%e);
    }
    
  • 1
    @ 2017-06-09 13:53:55

    蛤蛤蛤蛤蛤蛤第100条题解!!!
    只要exgcd求就行了,但同余式右方不是1而是两地的距离之差,编程要考虑到这点,否则。。。你懂得。。。
    另外,用longlong,否则。。。你还是懂的。。。
    #include<stdio.h>
    using namespace std;
    long long x,y,m,n,l,g,r,rr;
    void exgcd(long long d,long long f){
    if(!f){x=1,y=0,g=d;return;}
    exgcd(f,d%f);
    r=x,x=y,y=r-d/f*y;
    }
    int main(){
    // freopen("in.txt","r",stdin);
    // freopen("cuo.txt","w",stdout);
    scanf("%d%d%d%d%d",&x,&y,&m,&n,&l);
    n%=l,m%=l;
    if(m<=n)
    rr=(x-y+l)%l,exgcd(n-m,l);
    else
    rr=(y-x+l)%l,exgcd(m-n,l);
    // rr=(y-x+l)%l,exgcd((m-n+l)%l,l);
    if(!(rr%g)){rr=rr/g*x,rr%=l/g;if(rr<0)rr+=l/g;printf("%lld",rr);}
    else puts("Impossible");
    // printf("x=%d y=%d m=%d n=%d l=%d g=%d",x,y,m,n,l,g);
    // fclose(stdin);
    // fclose(stdout);
    return 0;
    }

  • 1
    @ 2016-07-09 15:26:49
    #include <iostream>
    using namespace std;
    typedef long long Long;
    inline Long abs(Long l) {
        return l<0?-l:l;
    }
    Long x0, y0;
    Long x,y,m,n,L;
    Long gcd(Long a, Long b) {
        Long t, d;
        if (b == 0) {
            x0 = 1;
            y0 = 0;
            return a;
        }
        d = gcd(b, a % b);
        t = x0;
        x0 = y0;
        y0 = t - a / b * y0;
        return d;
    }
    int main(int argc,char*argv[]) {
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cin>>x>>y>>m>>n>>L;
        x=x%L,y=y%L;
        if(x>y) {
            Long t = y;
            y = x,x = t,t = n,n = m,m = t;
        }
        Long a = abs(m - n);
        Long b = -L;
        Long c;
        if (m > n)
            c = y - x;
        else
            c = x - y + L;
        Long d = gcd(a, b);
        if (c % d != 0)
            cout<<"Impossible\n";
        else {
            Long add1 = x0 * c / d;
            Long add2 = abs(b / d);
            while (add1 < 0)
                add1 += add2;
            while (add1 - add2 >= 0)
                add1 -= add2;
            cout<<add1<<"\n";
        }
        return 0;
    }
    
  • 0
    @ 2009-10-26 19:55:55

    这道题为什么要用ax+by=c呢,追及1圈肯定有交点,为什么一定要整数天

    • @ 2015-10-25 16:17:24

      他们出题从来不考虑实际情况

  • 0
    @ 2009-08-18 23:26:29

    裴蜀等式+一次不定方程构造 小数学

  • 0
    @ 2009-08-04 15:21:16

    pku青蛙的约会

  • 0
    @ 2009-08-03 17:57:36

    如对本题有疑问可以参看我的题解:http://xujieqi.blog.hexun.com/35722312_d.html

  • 0
    @ 2009-07-31 09:00:22

    哇哈哈!!!第600人。。。

    Flag    Accepted

    题号   P1009

    类型(?)   数论 / 数值

    通过   600人

  • 0
    @ 2009-07-25 17:41:55

    var temp,n,m,x,y,l,c,d,a,b:int64;

    function gcd(a,b:int64;var x,y:int64):int64;

    var x1,y1:int64;

    begin

    if a mod b=0 then begin gcd:=b;x:=0;y:=1;exit;end;

    x1:=0;y1:=0;

    gcd:=gcd(b,a mod b,x1,y1);

    x:=y1;

    y:=x1-y1*(a div b);

    end;

    begin

    readln(x,y,m,n,l);

    if(m=n)and((x-y)mod l0)then begin writeln('Impossible');halt;end;

    if m>n then begin a:=m-n;b:=l;c:=((y-x)mod l+l)mod l;end;

    if n>m then begin a:=n-m;b:=l;c:=((x-y)mod l+l)mod l;end;

    d:=gcd(a,b,x,y);x:=x*c div d;

    if c mod d0 then begin writeln('Impossible');halt;end;b:=b div d;

    x:=(x mod b+b)mod b;

    writeln(x);

    end.

  • 0
    @ 2009-07-22 18:15:16

    “与此同时,出众的他也被世界各国遣清使臣所折服”

    ?????

    这句话有语病。

  • 0
    @ 2009-07-20 11:35:15

    Program P1009;

    var

    x,y,m,n,l,v,s,t,k,a:int64;

    Function gcd(a,b:int64):int64;

    var

    p:int64;

    begin

    while b>0 do

    begin

    p:=a mod b;

    a:=b;

    b:=p;

    end;

    exit(a);

    end;

    Function Find(a,b:int64):int64;

    var

    x,y,c:array [1..32] of int64;

    m,i:longint;

    p:int64;

    begin

    fillchar(x,sizeof(x),0);

    fillchar(y,sizeof(y),0);

    fillchar(c,sizeof(c),0);

    m:=0;

    while b>0 do

    begin

    inc(m);

    c[m]:=a div b;

    p:=a mod b;

    a:=b;

    b:=p;

    end;

    x[m+1]:=1;

    y[m+1]:=0;

    for i:=m downto 1 do

    begin

    x[i]:=y;

    y[i]:=x-c[i]*y;

    end;

    exit(x[1]);

    end;

    begin

    readln(x,y,m,n,l);

    while x

  • 0
    @ 2009-07-20 11:18:05

    program aa;

    var xx,yy,m,n,l,d,ans,t,tt,p,x,y,ttt:int64;

    function egcd(a,b:int64;var x,y:int64):int64;

    begin

    if b=0 then

      begin

       egcd:=a;

       d:=a;

       x:=1;

       y:=0;

      end

    else

      begin

       egcd(b,a mod b,x,y);

       t:=x;//x'

       x:=y;//y'

       y:=t-(a div b)*x;

      end;

    end;

    begin

    readln(xx,yy,m,n,l);

    ans:=-1;

    tt:=(yy-xx) mod l;

    egcd(m-n,l,x,y);

    if (tt mod d0) then begin writeln('Impossible'); halt;end;

    x:=x*(tt div d);

    x:=x-(x div l)*l;

    while x0 do x:=x-l;

    writeln(x);

    end.

  • 0
    @ 2009-07-18 21:39:58

    这个题目对我有难度,有哪位好心的大哥大姐能帮帮我啊

  • 0
    @ 2009-07-15 09:24:36

    最后一个点怎么回事?

  • 0
    @ 2009-07-13 15:39:37

    这题是纯数学,设k天后两人相遇,则问题变成了求同余方程x+kn≡y+km (mod L)。

    稍微整理一下,得到k(n-m)≡y-x (mod L) 的形式,其中k是未知数,所以就变成了

    求形如 ax≡b(mod n)的最小正整数解x。

    在处理时,无解直接就输出impossible,同时需要注意变量的正负和上限。

    答案的4开始我也搞不清,后来才明白,其实是向右走,不是向左走⊙﹏⊙

  • 0
    @ 2009-07-10 20:36:46

    晕,向西竟向右走...

  • 0
    @ 2009-07-06 20:16:58

    n*k mod l +y=m*k mod l +x?

信息

ID
1009
难度
8
分类
数论 点击显示
标签
递交数
6782
已通过
966
通过率
14%
被复制
9
上传者