• 线性同余方程一例:POJ 青蛙的约会

    线性同余方程的解决
    服务器君一共花费 54.109 ms 进行了 3 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

    为了熟悉欧几里德算法,我们再来看一个ACM题:

    Description:

    两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

    Input:

    输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。

    Output:

    输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行"Impossible"

    Sample Input:

    1 2 3 4 5

    Sample Output:

    4

    先考虑两只青蛙在怎样的情况下会碰面。就是它们跳了若干圈之后,他们同时落在某个点上:

    ( x+ m*s  ) - ( n*s + y ) = k*L;
    

    s 代表他们跳的步数,k 代表他们在第几圈相遇。

    我们把这个方程变形一下:

    x + m*s - n*s - y = k*L;
    x - y = k*L - m*s + n*s;
    s * ( n - m )  + k*L = x - y;
    

    这个方程就是所谓的线性同余方程,对于这种方程,如果有解必须满足 (x - y) % gcd ( n-m, L )==0 不然就无解, 输出Imposible。

    线性同余方程可以用扩展欧几里德算法解决。关于扩展欧几里德算法这里就不多说了,参照本专题的其它小节介绍。程序如下:

    #include "stdio.h"
    
    typedef long long BIG;
    
    BIG egcd(BIG a, BIG b, BIG *x, BIG *y) {
        BIG d, x1, y1;
        if (b == 0) {
            d = a;
            *x = 1;
            *y = 0;
        }
        else {
            d = egcd(b, a % b, &x1, &y1);
            *x = y1;
            *y = x1 - a / b * y1;
        }
        return d;
    }
    
    main() {
        BIG a, b, x, y, m, n, L, d;
        while(scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &L) != -1) {
            a = m < n ? n - m : m - n;
            b = m < n ? x - y : y - x;
            b = (L + b) % L; // avoid negative b
            d = egcd(a, L, &x, &y);
            if ( b % d)
                printf("Impossible\n");
            else {
    			/*hanldle negative answer case. e.g. 12 x == 20 (mod 28)*/
                for(x *= b / d, L /= d; x < 0; x += L); 
                printf("%lld\n", x % L);
            }
        }
    }
    
更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [计算机算法] 两数交换的各种算法细节 2 个条目
  2. [Python程序设计] 从PHP到Python 3 个条目
  3. [JavaScript程序设计] Web实时通信技术名词解析 5 个条目
  4. [移动开发] Android View注入框架Butter Knife 3 个条目
  5. [移动开发] Android抽屉导航NavigationDrawer 5 个条目
  6. [Python程序设计] Django后台管理系统 2 个条目
  7. [智力开发与知识管理] 整体性学习策略 9 个条目
  8. [软件工程与项目管理] 呈现树的构建 13 个条目
  9. [搜索引擎优化] 与百度权重有关的信息 2 个条目
  10. [搜索引擎优化] 百度搜索引擎优化指南 3 个条目
  11. [数据库技术] 无限级分类数据表设计 4 个条目
  12. [运维管理] 路由器与交换机 4 个条目
窗口 -- [博客]