2014
02-24

Running a paper shop is not an easy job, especially with harsh customers. Today they brought their own rectangular sheets of paper, asking you to cut it into rectangular business cards of specific size.

Moreover, they require that all the paper (which may not be cheap, but is definitely not that expensive!) has to be used, i.e. no tiny bit may be left over.
Moreover, the brilliant idea of cutting the sheet into very small pieces, and then gluing them together in desired sheets was laughed at.

An example of a 9 *6 paper sheet divided into 2 * 3 cards is given below.

The input contains several test cases. The first line contains the number of test cases t (t <= 10^5). Then t test cases follow. Each of them consists of one line containing four integers a, b, c, d (1 <=a, b, c, d <= 10^9).

Numbers a and b are dimensions of each business card; c and d are dimensions of the paper sheet.

The input contains several test cases. The first line contains the number of test cases t (t <= 10^5). Then t test cases follow. Each of them consists of one line containing four integers a, b, c, d (1 <=a, b, c, d <= 10^9).

Numbers a and b are dimensions of each business card; c and d are dimensions of the paper sheet.

4
2 3 9 6
2 3 8 6
2 3 6 8
2 3 5 7

YES
YES
YES
NO

/*
* hdu2965/win.cpp
* Created on: 2012-11-4
* Author    : ben
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
typedef long long LL;
int gcd(int a, int b) {
int r;
while(b) {
r = a % b;
a = b, b = r;
}
return a;
}
inline bool judge2(int a, int b, int z) {
int x = 1;
while(a * x < z) {
if((z - a * x) % b == 0) {
return true;
}
x++;
}
return false;
}

inline bool judge(int x, int y, int n, int m) {
int t = gcd(x, y);
if(n % t != 0 || m % t != 0) {
return false;
}
x /= t, y /= t, m /= t, n /= t;
if(n % x == 0 && m % y == 0) {
return true;
}
if(n % y == 0 && m % x == 0) {
return true;
}
if(n % x == 0 && n % y == 0 && judge2(x, y, m)) {
return true;
}
if(m % x == 0 && m % y == 0 && judge2(x, y, n)) {
return true;
}
return false;
}
int get_int() {
int res = 0, ch;
while (!((ch = getchar()) >= '0' && ch <= '9')) {
if (ch == EOF)
return 1 << 30;
}
res = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9')
res = res * 10 + (ch - '0');
return res;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int T, x, y, n, m;
T = get_int();
while(T--) {
x = get_int();
y = get_int();
n = get_int();
m = get_int();
bool ret = judge(x, y, n, m);
puts(ret ? "YES" : "NO");
}
return 0;
}

1. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识，这句话用《爱屋及乌》描述比较容易理解……

2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。

3. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮