首页 > 代码库 > LA 4384
LA 4384
扩展欧几里得
#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#define maxn 3000009#define ll long longusing 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。