poj 1061ユークリッドアルゴリズム

3つのアルゴリズムがあります.1つは簡単なgcdアルゴリズムです.
その鍵はgcd(a,b)==gcd(b,a mod b)を証明することである.
gcd(a,b)はgcd(b,a mod b)を除去し,gcd(b,a mod b)はgcd(a,b)を除去することを除去性を用いて実証した.
d=gcd(a,b)、a mod b=a-(a/b)*bとするので、dはa mod bを除去することができ、dはbを除去することができるので、dはbとa mod bの様々な線形組合せを除去することができる.gcd(b,a mod b)はbとa mod bの最小線形組合せである.従ってdはgcd(b,a mod b)を除去することができる.同様にgcd(b,a mod b)がgcd(a,b)を除去することも証明できる.
二つ目は線形方程式ax+by=gcd(a,b)を解くことである.
gcd(a,b)=gcd(b,a mod b)
従ってgcd(b,a mod b)=bx_0 + (a mod b)y_0;なら
ではgcd(a,b)=bx_0 + (a - (a/b) * b) y_0;
だからgcd(a,b)=ay_0 + (x_0 - (a/b ) * y_0);
コード:

/**
 *DESCRIPTION:The implement of gcd(a ,b) and ax + by = gcd(a , b)
 *using the equation gcd(a ,b) = gcd(b, a mod b)
 *gcd(a, 0) = a
 */

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    else {
        return gcd(b, a % b);
    }
}

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

三:同余モード方程式を解く
ax == b (mod n)
アルゴリズムの導論には詳細な解釈がある
2つの定理があります.
(一):方程式に解があれば必ずgcd(a,n)|bがある
(二):方程式に解があればn/(gcd(a,n))個の解がある
ここで、最小正数解は(x 0+n)%(n/d)(d==gcd(a,n))である.
ここでa,bが負数であるかどうかは影響しない.
poj1061:

#include <iostream>
#include <stdio.h>
using namespace std;

void extended_eculid(long long a, long long b, long long &gcd_d, long long &x, long long &y) {
    if (b == 0) {
        gcd_d = a;
        x = 1;
        y= 0;
    }
    else {
        extended_eculid(b, a % b, gcd_d, y, x);
        y -= (a / b) * x;
    }
}

int main() {

    long long x, y, m, n, L;
    long long a, b, gcd_d, x_0, y_0, ans;
    while (scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &L) != EOF) {
        a = m - n;
        b = y - x;
        /*        if (a < 0) {
            a = -a;
            b = -b;
            }*/
        extended_eculid(a, L, gcd_d, x_0, y_0);
        if ((b % gcd_d) != 0) {
            cout << "Impossible" << endl;
        }
        else {
            ans = (x_0 * b / gcd_d) % L;
            ans = (ans + L) % (L / gcd_d);
            if (ans == 0) {
                ans += L;
            }
            cout << ans << endl;
        }
    }
    return 0;
}

そのうちans=0の場合は長さLを出力します!～