Điểm đến (Reaching Points) trong C++

Cho điểm bắt đầu (sx, sy) và đích (tx, ty). Phép biến đổi: (x,y) → (x, x+y) hoặc (x+y, y). Kiểm tra có đường đi từ bắt đầu đến đích không.

Ví dụ

(1,1) → (4,5): (1,1)→(2,1)→(3,1)→(4,1)→(4,5) → true.

Thuật toán ngược (từ đích về đầu)

Trong khi tx > sx && ty > sy: nếu tx > ty thì tx %= ty else ty %= tx. Cuối cùng kiểm tra điều kiện dừng.

Chương trình C++

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

class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while(tx > sx && ty > sy) {
            if(tx > ty) tx %= ty;
            else ty %= tx;
        }
        return (sx == tx && sy <= ty && (ty - sy) % tx == 0) ||
               (sy == ty && tx >= sx && (tx - sx) % ty == 0);
    }
};

int main() {
    Solution ob;
    cout << ob.reachingPoints(1,1,4,5); // 1 (true)
    return 0;
}