注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2299][HAOI2011]向量  

2014-12-17 19:08:11|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2299: [HAOI2011]向量

一开始脑抽理解错题WA了
然后胡乱搞了半天不知道为啥A了……?

跪求神犇证明QAQ

题解在代码下方

#include<cstdio>
typedef long long ll;
int n,m;
int scan(){int i=0;scanf("%d",&i);return i;}
//ll scan(){ll i=0;scanf("%lld",&i);return i;}
ll gcd(ll a,ll b){return a?gcd(b%a,a):b;}
ll abs(ll a){return a<0?-a:a;}
int main(){
int i,j;
n = scan();
int a,b,x,y;
ll tmp[3];
for(i=1;i<=n;i++){
a = scan();b = scan();
x = scan();y = scan();
if(a<0)a=-a;
if(b<0)b=-b;
if(!a){
if(x%b==0 && y%b==0)printf("Y\n");
else printf("N\n");
}else if(!b){
if(x%a==0 && y%a==0)printf("Y\n");
else printf("N\n");
}else{
j = gcd(a,b);
if(x%j==0 && y%j==0){
j = gcd((ll)a+b,(ll)a-b);
if(abs((ll)x+y)%j==0)printf("Y\n");
else printf("N\n");
}else printf("N\n");

}
}
return 0;
}

题解:
数论。
问题是是否存在整数A,B,C,D使得
(A+B)*a + (C-D)*b = x
(C+D)*a + (A-B)*b = y
首先如果a=0||b=0特判
否则,对于某个单独方程先判断是否可能有解
以①为例:
令k = gcd(a,b)
若x%k=0则有解
但是这样只能保证
存在整数(A+B),(C-D)使①成立 
存在整数(C+D),(A-B)使②成立
使③=①+②
得到
(a+b)*(A+C) + (a-b)*(B+D) = x+y
再同①判断一下是否有解,如果有
这样就再能保证存在整数(A+C),(B+D)使①②同时成立

然后就得到存在整数A,B,C,D使得①②同时成立?
不知道为啥……
  评论这张
 
阅读(174)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017