cf1091div2 C.Grid Covering（数论）

Problem - C - Codeforces保证遍历完每行每列所以gcd(n,a)1,gcd(m,b)1很好理解为了遍历所有网格因为在2*lcm(n,m)次数后会再次踏上轮回重复循环此时访问了2*lcm(n,m)个格子于是 2*lcm(n,m)n*m也就是2*lcmgcd(n,m)*lcm(n,m)。所以 gcd(n,m)2#includebits/stdc.h using namespace std; #define ll long long #define endl \n const int N2e510; int n,m,a,b; int gcd(int a,int b) { return b0?a:gcd(b,a%b); } void solve() { cinnmab; if (gcd(n, a) 1 gcd(m, b) 1gcd(n,m)2 ){ coutYESendl; } else { coutNOendl; } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t1; cint; while(t--){solve();} return 0; }