HDU 5114 扩展欧几里得

题目大意：给你两个球的坐标 他们都往(1, 1)这个方向以相同的速度走，问你他们在哪个位置碰撞。

思路：这种题目需要把x方向和y方向分开来算周期，两个不同周期需要用扩展欧几里得来求第一次相遇。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define pii pair<int, int>

#define y1 skldjfskldjg

#define y2 skldfjsklejg

using namespace std;

const int N = 1e6 + ;

const int M = 1e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 +;

LL n, m, x1, x2, y1, y2;

LL exgcd(LL a, LL b, LL &x, LL &y) {

    if(!b) {

        x = ; y = ;

        return a;

    } else {

        LL gcd, t; gcd = exgcd(b, a % b, x, y);

        t = x; x = y; y = t - (a / b) * y;

        return gcd;

    }

}

int main() {

    int T; scanf("%d", &T);

    for(int cas = ; cas <= T; cas++) {

        LL t = -;

        scanf("%lld%lld%lld%lld%lld%lld", &n, &m, &x1, &y1, &x2, &y2);

        n <<= ; m <<= ; x1 <<= ; y1 <<= ; x2 <<= ; y2 <<= ;

        printf("Case #%d:\n", cas);

        LL ta = n - (x1 + x2) / ;

        LL tb = m - (y1 + y2) / ;

        if(x1 == x2 && y1 == y2) t = ;

        else if(x1 == x2) t = tb;

        else if(y1 == y2) t = ta;

        else {

            LL x, y, gcd;

            gcd = exgcd(n, m, x, y);

            if((tb - ta) % gcd == ) {

                x = (tb - ta) / gcd * x;

                x = (x % (m / gcd) + m / gcd) % (m / gcd);

                t = ta + n * x;

            }

        }

        if(t == -) {

             puts("Collision will not happen.");

        } else {

             x1 = (x1 + t) % ( * n);

             y1 = (y1 + t) % ( * m);

             if(x1 > n) x1 =  * n - x1;

             if(y1 > m) y1 =  * m - y1;

             printf("%.1f %.1f\n", x1 /2.0, y1 /2.0);

        }

    }

    return ;

}

/*

*/