1 条题解

  • 1
    @ 2026-8-26 20:38:13

    设 g=gcd(a,b)。

    1. 首先:(n,m) 必须都是 g 的倍数;否则 No。
    2. 全部除以 g:(a'=a/g;b'=b/g;n'=n/g;m'=m/g)。
    3. 若 (a',b') 均为奇数:则 (n'+m') 必须是偶数,Yes;否则 No。
    4. 若 (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;
    }
    

    信息

    ID
    802
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    47
    已通过
    9
    上传者