C++でポイントに到達する

開始点（sx、sy）と目標点（tx、ty）があるとすると、開始点から終了点までの一連の移動が存在するかどうかを確認する必要があります。ここでの移動は、点（x、y）を取得し、それを（x、x + y）または（x + y、y）に変換することで構成されます。

したがって、入力が（1、1）と（4,5）の場合、答えは真になります。これは、（1,1）を（2,1）、次に（3,1）、次に（4）に移動するためです。 、1）、次に（4,5）。

これを解決するには、次の手順に従います-

• tx>sxおよびty>syの場合、-
  を実行します。
  • tx> tyの場合、-
    • tx：=tx mod ty
  • それ以外の場合
    • ty：=ty mod tx
• return（sxがtxANDsyと同じ場合はtrue<=ty AND（ty --sy）mod txは0と同じ）OR（syはty AND x> =sx AND（tx --sx）modtyと同じは0）

理解を深めるために、次の実装を見てみましょう-

例

#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);
   }
};
main(){
   Solution ob;
   cout << (ob.reachingPoints(1,1,4,5));
}

入力

1
1
4
5

出力

1