UVA 618 - Doing Windows（数论）
标签：style blog http color io 2014
题目链接：618 - Doing Windows
题意：给定一个大小不能变的屏幕，和四个大小可以变的窗口，变化要保持长宽比，问这四个窗口能不能调整后全部放下正好填满屏幕，不能重叠
思路：情况一共就几种：4个叠一起，3个叠一起+一个，2个和2个，一个和两个叠一起在一个，把这几种情况全判断了就可以了，判断过程利用gcd，lcm可以求边长。
代码：
#include
#include
long long gcd(long long a, long long b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
return a / gcd(a, b) * b;
}
struct Win {
long long x, y;
bool scanf_() {
scanf("%lld%lld", &x, &y);
if (x == 0 || y == 0)
return false;
long long t = gcd(x, y); x /= t; y /= t;
return true;
}
void swap() {
long long t = x;
x = y;
y = t;
}
} win, w[4];
bool check1(Win a, Win b, Win c, Win d) {
long long sum = 0;
if (win.y % a.y)
return false;
sum += win.y / a.y * a.x;
if (win.y % b.y)
return false;
sum += win.y / b.y * b.x;
if (win.y % c.y)
return false;
sum += win.y / c.y * c.x;
if (win.y % d.y)
return false;
sum += win.y / d.y * d.x;
if (sum != win.x)
return false;
return true;
}
bool check(Win a, Win b, Win c, long long wx, long long wy) {
if (wy = win.y)
return false;
long long yy = win.y - wy;
if (judge2(a, b, c, win.x, yy))
return true;
if (yy % a.y) return false;
sum += yy / a.y * a.x;
if (yy % b.y) return false;
sum += yy / b.y * b.x;
if (yy % c.y) return false;
sum += yy / c.y * c.x;
int flag = 0;
if (sum == win.x) flag = 1;
return flag;
}
bool check3(Win a, Win b, Win c, Win d) {
long long sum = 0;
long long wy = lcm(a.y, b.y);
if (wy >= win.y)
return false;
sum += wy / a.y * a.x;
sum += wy / b.y * b.x;
if (win.x % sum)
return false;
if (win.y
UVA 618 - Doing Windows（数论）,搜素材,soscw.com
UVA 618 - Doing Windows（数论）
标签：style blog http color io 2014
原文地址：http://blog.csdn.net/accelerator_/article/details/24634197
评论