TIOJ 1982：奇幻反彈（Bouncing）

TIOJ 1982：奇幻反彈（Bouncing）

題目大意：在 $(a, b)$ 發球到點 $(c, d)$，求會彈到 $(ac - bd, bc + ad)$，現在給你 $6$ 個點 $(a_i, b_i)$ 代表從 $(p, q)$ 發球到 $(c_i, d_i)$ 彈到的座標，規定 $p, q, c_i, d_i$ 必須是整數，想找出 $p^2+q^2$ 最大能是多少，最後輸出 $|p|+|q|$。

解法：有點奇妙的一題，發現如果有兩個數 $a+bi, c+di$ 那它們相乘會是 $(ac-bd) + (bc+ad)i$，與上面的形式相同，我們想找出 $p+qi$，那 $\frac{a+bi}{p+qi}=c+di$，$c, d$ 必須是整數，如果換成一般整數的運算，可以去找最大公因數，那這題也是一樣，我們要找出複數的最大公因數，我們可以直接實作一個遞迴函式 $\gcd(a, b) = \gcd(b, a - b\times(a/b))$，因為 $a/b$ 可能不是整數，於是需要去看哪樣會使最後結果比較小，然後我有用到 $\text{__int128}$。

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int N = 6;

using i128 = __int128;
using cp = complex<i128>;

i128 abs (i128 x) {
    return x >= 0 ? x : -x;
}

cp operator % (cp a, cp b) {
    cp c = a / b, d = a - b * c;
    i128 mn = d.real() * d.real() + d.imag() * d.imag();
    FOR (dr, -1, 1) FOR (di, -1, 1) {
        cp tc = c + cp (dr, di), td = a - b * tc;
        i128 val = td.real() * td.real() + td.imag() * td.imag();
        if (val < mn) {
            mn = val;
            d = td;
        }
    }
    return d;
}

cp gcd (cp a, cp b) {
    return b == cp (0, 0) ? a : gcd (b, a % b);
}

cp G;

void solve() {
    for (int i = 0; i < N; i++) {
        ll a, b;
        cin >> a >> b;
        G = gcd (G, cp (a, b));
    }
    cout << (ll) (abs (G.real()) + abs (G.imag())) << '\n';
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！