Doveqise

Doveqise

万事皆虚,诸行皆允

CF1200C Round Corridor 题解

posted on 2019-08-12 21:24:38 | under 题解 |

这道题 一道数论题(小学奥数题)
我们通过看图 发现在12点方向以外,gcd(n,m)的整数倍地方有大墙
所以我们可以把内圈分成n/gcd(n,m)块,外圈分成m/gcd(n,m)块
然后判断两点是否在同一块内
暴力判断代码长的雅痞
旁边巨佬疯狂嘲讽我代码长
最后告诉我只要-1就可以
emmm
awcsl
下见代码(然鹅还是比旁边神仙长)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
signed main()
{
    int n,m,q;
    scanf("%lld%lld%lld",&n,&m,&q);
    int g=gcd(n,m);
    for(int i=1,sx,sy,ex,ey;i<=q;i++)
    {
        scanf("%lld%lld%lld%lld",&sx,&sy,&ex,&ey);
        if(sx==1) sy=(sy-1)/(n/g);
        else sy=(sy-1)/(m/g);
        if(ex==1) ey=(ey-1)/(n/g);
        else ey=(ey-1)/(m/g);
        puts(sy==ey?"YES":"NO");
    }
}