Hiểu bài toán

Bài toán yêu cầu xác định xem có thể di chuyển từ điểm M(u, v) đến điểm N(x, y) trên mặt phẳng tọa độ hay không. Các phép di chuyển hợp lệ từ một điểm (a, b) là đến các điểm (a+b, b), (a, a+b), (a-b, b) hoặc (a, b-a). Ta cần giải quyết t câu hỏi với các tọa độ lên tới 10^18.

Phân tích tính chất của các phép di chuyển:

• Các phép di chuyển này tương tự như thuật toán Euclid tìm ước chung lớn nhất (GCD).
• Điểm đặc biệt: GCD của hai số không thay đổi sau các phép di chuyển.
  • gcd(a+b, b) = gcd(a, b)
  • gcd(a, a+b) = gcd(a, b)
  • gcd(a-b, b) = gcd(a, b)
  • gcd(a, b-a) = gcd(a, b)
• Điều kiện cần để đi từ M đến N là gcd(u, v) = gcd(x, y).
• Để chứng minh điều kiện này là đủ, ta cần chỉ ra rằng từ bất kỳ cặp số nào (a, b) có GCD là g, ta có thể biến đổi về (g, g) (hoặc (g, 2g) hay các dạng đặc biệt).
  • Quy trình: Sử dụng các phép trừ (giống Euclid) để giảm một trong hai số, sau đó có thể dùng phép cộng để tạo ra số mới. Ví dụ, từ (g, g) ta có thể đến (g, 2g), (2g, g)... và từ đây đến bất kỳ cặp số nào có GCD là g. Vậy, lời giải là so sánh GCD của hai cặp số.

Các cách tiếp cận

Cách Giải thuật Euclid

#include <bits/stdc++.h>
using namespace std;

long long gcdll(long long a, long long b) {
    while (b) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        long long u, v, x, y;
        cin >> u >> v >> x >> y;
        if (gcdll(u, v) == gcdll(x, y)) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    return 0;
}

• Time Complexity: O(log(min(u, v))) cho mỗi truy vấn, tổng thể O(t * log(10^18)) ~ O(t * 60).
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp dựa trên tính chất GCD của các phép di chuyển.

1. Định nghĩa hàm tính ước chung lớn nhất (GCD) sử dụng thuật toán Euclid.
2. Với mỗi bộ test case, đọc 4 số u, v, x, y.
3. Tính GCD của cặp (u, v) và GCD của cặp (x, y).
4. Nếu hai giá trị GCD này bằng nhau, in ra 'YES', ngược lại in 'NO'.

Cách này利用了 thuật toán Euclid vốn rất hiệu quả để tính GCD cho số lớn, đảm bảo thời gian chạy nhanh chóng.

Cách Sử dụng hàm có sẵn

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    if (!(cin >> t)) return 0;
    while (t--) {
        long long u,v,x,y;
        cin >> u >> v >> x >> y;
        long long g1 = std::gcd(u,v);
        long long g2 = std::gcd(x,y);
        cout << (g1 == g2 ? "YES" : "NO") << '\n';
    }
    return 0;
}

• Time Complexity: O(log(min(u, v))) cho mỗi truy vấn.
• Space Complexity: O(1)

Đây là phiên bản tối ưu hóa code sử dụng thư viện chuẩn C++17 (và các thư viện khác).

1. Sử dụng hàm std::gcd có sẵn trong thư viện <numeric> (được bao gồm trong <bits/stdc++.h>).
2. Logic hoàn toàn tương tự như cách tiếp cận 1: so sánh GCD của hai cặp số.

Ưu điểm của cách này là code ngắn gọn, dễ đọc và ít lỗi chính tả hơn so với việc tự implement lại hàm GCD.

Cách Tối ưu hóa nhập xuất (I/O)

// Dưới đây là code tổng hợp tối ưu I/O và logic chuẩn
#include <bits/stdc++.h>
using namespace std;

void solve() {
    long long u, v, x, y;
    cin >> u >> v >> x >> y;
    // Sử dụng __gcd hoặc std::gcd
    if (__gcd(u, v) == __gcd(x, y)) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    // Tối ưu tốc độ nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

• Time Complexity: O(t * log(max_value))
• Space Complexity: O(1)

Trong lập trình thi đấu, tốc độ nhập xuất (I/O) có thể là bottle-neck khi xử lý số lượng lớn.

1. Sử dụng ios_base::sync_with_stdio(false); cin.tie(NULL); để tắt đồng bộ hóa với C-style I/O và bỏ việc flush output stream sau mỗi lần xuất, giúp tăng tốc độ đáng kể.
2. Logic vẫn giữ nguyên: kiểm tra điều kiện GCD.

Đây là cách tiếp cận 'chuẩn' trong thi đấu: kết hợp thuật toán đúng đắn với tối ưu hóa môi trường thực thi.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Các phép di chuyển giữ nguyên giá trị ước chung lớn nhất (GCD) của hai tọa độ.
• Điều kiện cần và đủ để đi từ M(u, v) đến N(x, y) là gcd(u, v) == gcd(x, y).
• Số 0 không xuất hiện trong input (số nguyên dương), nhưng thuật toán Euclid hoạt động chính xác với số dương.

Lỗi thường gặp

• Sử dụng sai kiểu dữ liệu: Input lên tới 10^18, bắt buộc phải dùng long long (hoặc int64_t) ở C++.
• Lỗi logic: Đánh đồng việc có thể đến được một điểm với việc có chung GCD là chưa đủ nếu không hiểu tính chất 'nhảy cóc' của phép cộng. Tuy nhiên, với số tự nhiên dương và phép trừ/ cộng như trên, ta luôn có thể tạo ra các số bù để đến được đích nếu chung GCD.
• Quên tối ưu I/O: Với t = 1000, I/O không tối ưu không致命 nhưng là thói quen xấu và có thể gây TLE trên một số ngôn ngữ chậm hơn hoặc input lớn hơn.