【题目描述】
寻找一个由n个整数组成的数列，其中任意连续p个整数之和为正，任意连续q个整数之和为负。若不存在这样的整数数列，则输出NO，否则输出其中一个数列。
【输入】
对于每个测试点将给你M组数据，要求你对于每组数据，判断是否存在这样的整数数列。
输入的第一行是一个正整数M，（1<=N<=10000）,接下来的M行对应M组数据，每行有三个正整数N、P、Q（1<=n,p,q<=10^8）。
【输出】
输出数据共N行，每行为yes或者no，如果第I组数据有解，则在第I行输出yes，否则输出no
【输入输出示例】
| 输入(sequence.in) | 输出(sequence.out) |
2
1 1 9
10 2 4 | yes
no |
【评分标准】
对于每个测试点，如果你能够在1S内通过每组数据，你将得到这个测试点的分数，否则，这个测试点你只能得0分。
【分析】
原题目是要求输出一种可能的解，如果没有解就输出-1。这样的话就要用到差分约束。
现在的话，只需要一个公式。如果有解，应满足：n<=q+p+gcd(p,q)-1。
1: #include <stdio.h>
2: #include <iostream>
3: using namespace std;
4:
5: int n,m,p,q;
6:
7: int gcd(int a,int b)
8: {
9: if (a<b) swap(a,b);
10: int t;
11: while (b!=0)
12: {
13: t=a;
14: a=b;
15: b=t%a;
16: }
17: return a;
18: }
19:
20: int main()
21: {
22: freopen("sequence.in","r",stdin);
23: freopen("sequence.out","w",stdout);
24:
25: scanf("%d",&m);
26: for (int i=0;i<m;++i)
27: {
28: scanf("%d%d%d",&n,&p,&q);
29: if (n<=p+q+gcd(p,q)-1) printf("YES\n");
30: else printf("NO\n");
31: }
32: return 0;
33: }
34: