Grid Covering (CF R 1091 Div.2 - C)

https://codeforces.com/contest/2217/problem/C

---

아이디어

만약 x축 이동과 y축 이동을 독립적으로 한다고 생각해봅시다. 그러면 항상 (+a,+b)의 이동만 하게 됩니다. 그러면 gcd(N,a)==1임을 알 수 있습니다. 만약 이 값이 1이 아니라 g라고 한다면, 이동 가능한 x좌표는 g로 나눈 나머지가 1인점밖에 없음을 알 수 있습니다. 그러므로 gcd(N,a)==1입니다. 마찬가지로 gcd(M,b)==1입니다.

 

근데 이 조건만 만족한다고 되는것은 아닙니다. 만약 N번의 이동을 했다면, x좌표가 다시 1이 됩니다. 이때의 y좌표는 b*N%M+1이 됩니다. 그런데 이 값에서 1을 뺀 값, 즉 b*N%M이 M과 서로소가 아니라면, 아까와 마찬가지의 이유로 x좌표가 1인 위치에서는 y좌표가 한정될 수 밖에 없습니다. 그러므로 b*N%M은 M과 서로소여야만합니다. b*N이 M과 서로소인것과 동치이며, gcd(b,M)==1이므로 gcd(N,M)==1인것과 동치입니다.

 

그런데 이 문제에서는 x축 이동과 y축 이동을 순서대로합니다. 그러므로 gcd(N,M)==2이여도 x축 이동을 먼저 함으로써 그 공백을 채울 수 있습니다. 그러므로 gcd(N,M)<=2이며, gcd(N,a)==gcd(M,b)==1일때 가능하게 됩니다.

---

 소스코드

#include <iostream>
#define ll long long
using namespace std;

ll gcd(ll a,ll b){return ((b)?gcd(b,a%b):a);}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll T,N,M,a,b;

    cin>>T;
    while (T--)
    {
        cin>>N>>M>>a>>b;

        if ((gcd(N,M)<=2) && gcd(N,a)==1 && gcd(M,b)==1) cout<<"YES\n";
        else cout<<"NO\n";
    }
}