math - 可能的路径 [HackerRank]

Question

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

Adam is standing at point (a,b) in an infinite 2D grid. He wants to know if he can reach point (x,y) or not. The only operation he can do is to move to point (a+b,b), (a,a+b), (a-b,b), or (a,a-b) from some point (a,b). It is given that he can move to any point on this 2D grid,i.e., the points having positive or negative X(or Y) co-ordinates.Tell Adam whether he can reach (x,y) or not.

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

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

所以 x%(a+b) OR x%(a-b) 应该能被 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