题目

源地址：

http://poj.org/problem?id=1061

理解

扩展欧几里德方程的模板体。当初没有做出来，现在好像明白一点了。

新技能get

扩展欧几里德方程解法

设标准方程式为： ax +by =d (a,b已知)

  1. 首先求出gcd(a,b) ，然后化简方程，使得a/=gcd(a,b); b/=gcd(a,b); d/=gcd(a,b);
  2. 先求出 ax+by=gcd(a,b) 的一组特解，也就是方程 ax+by=1 的一个特解。然后将特解（x0, y0） 代入方程，并变形： a* x0 d + b y0 *d= d
  3. 根据解系的 公式： x =x1 + b* t ; y =y1 - a t; 我们首先假设他最小的解x=0 ，然后求出 此时的 t=-x1/b; 然后带入求最小的解x=x1+bt=x1 - b*t ;因为此时的t为 负数， 减去他的 负数，就是等于加上他。

代码

#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;


long long x, y, m, n, l;
long long a, b, d, k, s, t;

long long gcd(long long a, long long b)
{
    long long c;
    if (a < b)
    {
        c = a;    a = b;
        b = c;
    }
    while (b)
    {
        c = b;
        b = a % b;
        a = c;
    }
    return a;
}

long long extended_gcd(long long a, long long b, long long &x, long long &y)
{
    long long ans, t;
    if (b == 0)
    {
        x = 1;    y = 0;
        return a;
    }
    else
    {
        ans = extended_gcd(b, a % b, x, y);
        t = x;    x = y;
        y = t - (a / b) * y;
    }
    return ans;
}

int main(int argc, char const *argv[])
{
    while (scanf("%lld %lld %lld %lld %lld", &x, &y, &m, &n, &l) != EOF)
    {
        a = n - m;
        b = l;
        d = x - y;
        long long r = gcd(a, b);
        if (d % r != 0)
        {
            printf("Impossible\n");
            continue;
        }
        a /= r;
        b /= r;
        d /= r;
        extended_gcd(a, b, s, k);
        s = s * d;
        k = k * d;
        t = s / b;
        s = s - t * b;
        if (s < 0)
            s += b;
        printf("%lld\n", s);
    }
    return 0;
}

更新日志

  • 2014年07月23日 已AC。