首页 > 其他 > 详细

LA 4384

时间:2014-07-18 19:38:44      阅读:402      评论:0      收藏:0      [点我收藏+]

扩展欧几里得

bubuko.com,布布扣
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 3000009
#define ll long long
using namespace std;

void gcd(ll a,ll b,ll& d,ll& x,ll &y)
{
    if(!b){d=a;x=1;y=0;}
    else {gcd(b,a%b,d,y,x);y-=x*(a/b);}
}

bool check(ll a,ll b,ll n)
{
    ll d,x,y;
    gcd(a,b,d,x,y);
    if(n%d)return 0;
    a/=d;b/=d;n/=d;
    x*=n;y*=n;
    if(x<0){swap(x,y);swap(a,b);}
    return y+a*(x/b)>=0;
}

bool yes(ll a,ll b,ll x,ll y)
{
    if((x%a==0&&y%b==0)||(x%b==0&&y%a==0))
       return 1;
    return 0;
}

int main()
{
    int t;
    ll a,b,x,y;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld%lld",&a,&b,&x,&y);
        if((x%a==0&&x%b==0&&check(a,b,y)||(y%a==0&&y%b==0&&check(a,b,x))||yes(a,b,x,y)))
            puts("YES");
        else puts("NO");
    }
    return 0;
}
View Code

LA 4384,布布扣,bubuko.com

LA 4384

原文:http://www.cnblogs.com/yours1103/p/3850614.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!