【題目描述】
尋找一個由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: