1 条题解
-
1
设 g=gcd(a,b)。
- 首先:(n,m) 必须都是 g 的倍数;否则 No。
- 全部除以 g:(a'=a/g;b'=b/g;n'=n/g;m'=m/g)。
- 若 (a',b') 均为奇数:则 (n'+m') 必须是偶数,Yes;否则 No。
- 若 (a',b') 一奇一偶:直接 Yes。
原理: 每一步坐标变化:(Δx+Δy) 的奇偶:
- a,b 均奇数:(Δx+Δy)永远偶数,所以目标坐标和必须偶数。
- 一奇一偶:可以改变奇偶,任何点都可达。
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } int main() { int T; cin>>T; while(T--) { ll a,b,n,m; cin >> a >> b >> n >> m; ll g = gcd(a,b); if(n % g != 0 || m % g != 0) { cout << "No\n"; continue; } a /= g; b /= g; n /= g; m /= g; if((a & 1) && (b & 1)) { if((n + m) % 2 == 0) cout << "Yes\n"; else cout << "No\n"; } else { cout << "Yes\n"; } } return 0; }
- 1
信息
- ID
- 802
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 47
- 已通过
- 9
- 上传者