这题忘了开long long了,以后数论题尽量都开long long吧。。。
三种情况1、全部横着放
2、全部竖放
3、横竖交叉放,其中一条边要是a,b最小公倍数的倍数,另外一边直接解模线性方程
#include<stdio.h>
typedef long long LL;
LL getgcd(LL a,LL b)
{
if(!b)return a;
return getgcd(b,a%b);
}
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 calcu(LL a,LL b,LL x,LL y)
{
if(x<0)
{
while(x<0)
{
x+=b;
y-=a;
}
if(y>0)
return true;
}
else if(y<0)
{
while(y<0)
{
x-=b;
y+=a;
}
if(x>0)
return true;
}
return false;
}
int main()
{
int t;
LL a,b,c,d;
scanf("%d",&t);
while(t--)
{
scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&d);
if(c%a==0&&d%b==0||c%b==0&&d%a==0)
printf("YES\n");
else
{
LL p=getgcd(a,b);
if(c%p||d%p)
printf("NO\n");
else
{
a/=p;b/=p;
c/=p;d/=p;
LL x,y,gg=a*b,v;
if(c%gg==0)
{
//printf("d=%d,",d);
gcd(a,b,v,x,y);
//printf("x=%d,y=%d\n",x,y);
if(calcu(a,b,x*d,y*d))
{
printf("YES\n");
continue;
}
}
if(d%gg==0)
{
//printf("c=%d,",c);
gcd(a,b,v,x,y);
//printf("x=%d,y=%d\n",x,y);
if(calcu(a,b,x*c,y*c))
{
printf("YES\n");
continue;
}
}
printf("NO\n");
}
}
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
2019 Multi-University Training Contest 4(2019hdu多校第六场数据与标程)
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
此程序为hdu的acm2010题,就是解决水仙花数问题
杭电hdu acm资料所用杭电的acm题
包含实验内容:对应实验要求上的1/2/3/5实验,分别为setName/setNice,petree输出进程,模拟shell,进程通信,文件系统。包含全部实验源代码和详尽的word实验报告。同时包含在线PTA编程题目:进程模拟,模拟进程调度...
HDU一部分题目原码,大部分是可运行的,可能有几题不完整
杭电 hdu acm 第1084题的解法,ac过了,是一位学长教我的.内有一些中文说明.
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
hdu 1005.比较简单的一道题,有兴趣的可以看看。
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
100道 acm C语言 hdu 解题报告
ACM hdu 代码大全3000例,hdu已经AC的3000例代码,部分代码有详细解析
HDU1059的代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
HDU2013暑期多校联合训练第一场0723-解题报告和标程
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了