可能的路径 [HackerRank]

Question

请参阅最近在 HackerRank 上发布的以下问题

Adam 站在无限二维网格中的 (a,b) 点。他想知道他是否可以到达点 (x,y)。他唯一能做的操作就是从某个点 (a,b) 移动到点 (a+b,b)、(a,a+b)、(ab,b) 或 (a,ab)。假设他可以移动到这个二维网格上的任何点，即X（或Y）坐标为正或负的点。告诉Adam他是否可以到达（x，y）。

https://www.hackerrank.com/contests/infinitum-jun14/challenges/possible-path

我意识到 x 和 y 必须是 a 和 b 的某个倍数之和......

所以 x%(a+b) OR x%(ab) 应该能被 a 或 b 整除，对于 y 也是如此...

但以下不起作用...

    long long int xb,yb,xa,ya;
    xb = x % b;
    xa = x % a;
    yb = y % b;
    ya = y % a;

    // for x
    bool cxbaplusb = a+b==0 ? xb == 0: (xb%(a+b))==0;
    bool cxbaminb = a-b==0 ? xb == 0: (xb%(a-b))==0;

    // for y
    bool cybaplusb = a+b==0 ? yb == 0: (yb%(a+b))==0;
    bool cybaminb = a-b==0 ? yb == 0: (yb%(a-b))==0;

    // for x
    bool cxaaplusb = a+b==0 ? xa == 0: (xa%(a+b))==0;
    bool cxaaminb = a-b==0 ? xa == 0: (xa%(a-b))==0;

    // for y
    bool cyaaplusb = a+b==0 ? ya == 0: (ya%(a+b))==0;
    bool cyaaminb = a-b==0 ? ya == 0: (ya%(a-b))==0;

    if ( (cxbaplusb || cxbaminb || cxaaplusb || cxaaminb)  && (cybaplusb || cybaminb || cyaaplusb || cyaaminb) )        
        std::cout << "YES" << std::endl;
    else
        std::cout << "NO" << std::endl;      

但这不起作用......我缺少任何条件吗？有什么建议 ？？

Answer 1

以下数学解释可能会帮助您实现目标。

资料来源：https ://hr-filepicker.s3.amazonaws.com/infinitum-jun14/editorials/2372-possible-path.pdf