110 条题解

  • 0
    @ 2007-08-20 23:10:24

    TNND,居然有我们大汉在月式的西边的事情。对于不完全用exgcd的我们来说,这个数据太烂了。

  • 0
    @ 2007-07-31 19:47:19

    是不是样例有问题?按题目的算法,就是追击问题吧,右边的与左边的差一个单位,而速度也差一个单位,正好一天可以赶上来啊!为什么要4天?

    是不是题目出问题,是应该往右走的?

  • 0
    @ 2007-07-16 22:26:51

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    好久了, 终于AC了!! 庆祝!

    求解线性模方程, 数据有些大, 应用long long存储

    还有就是注意正副的问题, 已经取最小的天数.

  • 0
    @ 2007-06-19 16:41:28

    var

    x,y,m,n,l:integer;

    a,b,c,t:real;

    begin

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

    b:=x-y;

    c:=b*l/360;

    t:=c/(m-n);

    if t>1000000

    then

    writeln('impossible');

    writeln(t);

    end.

  • 0
    @ 2007-06-04 19:47:39

    显然,原题可化为求P*V MOD L=K 中 Pmin(P>=0)(V为速度差,K为两人的距离)(不妨定义Pmin=F(V,L,K))

    设P*V-Q*L=K(Q>=0)则求Pmin相当于求Qmin

    又Q*L=P*V-K得Q*L MOD V=(-K) MOD V,

    于是F(V,L,K)=(Qmin*L+K) DIV V=(F(L MOD V,V,(-K)MOD V)*L+K)DIV V;

    边界条件自己找吧

  • 0
    @ 2007-03-24 17:48:08

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

  • 0
    @ 2006-12-17 11:31:43

    怎么回事????

  • 0
    @ 2006-12-10 11:23:40

    我RP--,Cheat的……

  • 0
    @ 2006-11-15 22:18:34

    扩展欧几里德算法?

    有没有大牛能讲得我们普通人都懂啊?

    如果没有的话,暂时放弃了~~~5555555

  • 0
    @ 2006-10-22 14:19:28

    本人看不懂扩展欧几里德算法,于是自己编了一个自己推算的程序

    a*k=b( mod c)

    ---|-->a*k=b+c*l---|-->c*l=-b+a*k---|->c*l=-b ( mod a)

    把原方程转化为规模较小的方程,递归求解。。。。

    边界条件:b mod a=0 时k= b div a;a=0时无解

    。。。。。。int64卡了我好久

  • 0
    @ 2006-10-08 21:47:22

    首先将题目转化为at-kl=b的情况,这里a和k均是未知量,

    那么方程无解的情况就是r=gcd(t,l)不能整除b,(即b%r!=0)

    如果可以那么分别用t/r,l/r,b/r来代替t, l ,b,

    然后利用个扩展欧几里德算法得到c,d使得ct+dl=1,

    如果c

  • 0
    @ 2006-10-01 17:37:54

    还有一种无解情况是两个速度都为偶数,而距离差为奇数。

  • 0
    @ 2006-03-25 10:10:42

    首先求出相对速度和距离,再和L一起列出vx+ly=c(C是相对距离)

    然后是用吴文虎教授黑书上62页的欧几里德推广算法求出一个解.

    再求出X的周期,求出X的最小整数值即可.

  • 0
    @ 2006-03-23 12:19:38

    数据太大了,必须用高效算法。

    那些普通的算法不够的。

    标称的难度才那么点点,太迷惑人了。

  • 0
    @ 2006-02-04 09:44:33

    直接说扩展辗转相除法就好了。

  • 0
    @ 2006-01-22 16:13:00

    根据题意,即有(m-n)*A-l*B≡y-x,即使用扩展欧几里德算法解关于未知整数A和B的同余方程即可。注意处理m-n、y-x和x=y的值小于零的情况,且当m=n时,直接判断其无解。需要注意的是,运算中和结果数据很可能超出231-1,建议使用Int64类型。

  • -1
    @ 2022-04-09 15:35:32
    
    #include<stdio.h>
    #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
    @ 2021-11-10 12:29:15
    #include<bits/stdc++.h>
    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;
    }
         
    
    
  • -1
    @ 2019-05-11 20:16:48

    1 0000 0000 mod 1 !!!!
    看清楚,是模1!
    模1就只有零了!

  • -1
    @ 2016-10-25 17:40:46

    begin
    write('Impossible');
    end.

    两个点···

信息

ID
1009
难度
8
分类
数论 点击显示
标签
递交数
6992
已通过
1056
通过率
15%
被复制
27
上传者