【題目描述】
尋找一個由n個整數(shù)組成的數(shù)列，其中任意連續(xù)p個整數(shù)之和為正，任意連續(xù)q個整數(shù)之和為負(fù)。若不存在這樣的整數(shù)數(shù)列，則輸出NO，否則輸出其中一個數(shù)列。
【輸入】
對于每個測試點將給你M組數(shù)據(jù)，要求你對于每組數(shù)據(jù)，判斷是否存在這樣的整數(shù)數(shù)列。
輸入的第一行是一個正整數(shù)M，（1<=N<=10000）,接下來的M行對應(yīng)M組數(shù)據(jù)，每行有三個正整數(shù)N、P、Q（1<=n,p,q<=10^8）。
【輸出】
輸出數(shù)據(jù)共N行，每行為yes或者no，如果第I組數(shù)據(jù)有解，則在第I行輸出yes，否則輸出no
【輸入輸出示例】
| 輸入(sequence.in) | 輸出(sequence.out) |
2
1 1 9
10 2 4 | yes
no |
【評分標(biāo)準(zhǔn)】
對于每個測試點，如果你能夠在1S內(nèi)通過每組數(shù)據(jù)，你將得到這個測試點的分?jǐn)?shù)，否則，這個測試點你只能得0分。
【分析】
原題目是要求輸出一種可能的解，如果沒有解就輸出-1。這樣的話就要用到差分約束。
現(xiàn)在的話，只需要一個公式。如果有解，應(yīng)滿足：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: