频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
hdu 4596 Yet another end of the world(数论)
2014-04-26 11:06:48         来源:hdu 4596 Yet another end of the world(数论)  
收藏   我要投稿

题目链接:4596 Yet another end of the world


题目大意:给定若干组x,y,z,问是否能找到一个整数d,使得至少两组x,y,z满足y≤d%x≤z。


解题思路:首先枚举出两组x,y,z。

然后判断这两组是否能找到一个d,使得满足题目条件。

现在假设a、b,有a*x1+y1≤d≤a*x1+z1和b*x2+y2≤d≤b*x2+z2;

若两段区间有交集,必有a*x1+y1≤b*x2+z2且b*x2+y2≤a*x1+z1;

化简得a*x1-b*x2≤z2-y1 且a*x1-b*x2≥y2-z1;

若a,b有整数解,根据拓展欧几里得定理ax1+bx2=u有整数解的情况为u/gcd(x1,x2)==0;

所以若存在y2-z1≤u≤z2-y1,使得u/gcd(x1,x2)==0即可。


#include 
#include 

const int N = 1005;

int n, x[N], y[N], z[N];

int gcd (int a, int b) {
	return b == 0 ? a : gcd(b, a%b);
}

bool judge (int t, int a, int b) {
	if (a % t == 0 || b % t == 0) return true;
	if (a < 0 && b > 0) return true;
	if (b/t - a/t >= 1) return true;
	return false;
}


bool solve () {
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int t = gcd(x[i], x[j]);
			if (judge(t, y[j]-z[i], z[j]-y[i])) return false;
		}
	}
	return true;
}

int main () {
	while (scanf("%d", &n) == 1) {
		for (int i = 0; i < n; i++)
			scanf("%d%d%d", &x[i], &y[i], &z[i]);
		printf("%s\n", solve () ? "Can Take off" : "Cannot Take off");
	}
	return 0;
}


点击复制链接 与好友分享!回本站首页
相关TAG标签 数论
上一篇:hdu 4497 GCD and LCM(组合数学)
下一篇:c++学习笔记之成员模板
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站