【題目描述】
尋找一個(gè)由n個(gè)整數(shù)組成的數(shù)列，其中任意連續(xù)p個(gè)整數(shù)之和為正，任意連續(xù)q個(gè)整數(shù)之和為負(fù)。若不存在這樣的整數(shù)數(shù)列，則輸出NO，否則輸出其中一個(gè)數(shù)列。
【輸入】
對(duì)于每個(gè)測(cè)試點(diǎn)將給你M組數(shù)據(jù)，要求你對(duì)于每組數(shù)據(jù)，判斷是否存在這樣的整數(shù)數(shù)列。
輸入的第一行是一個(gè)正整數(shù)M，（1<=N<=10000）,接下來(lái)的M行對(duì)應(yīng)M組數(shù)據(jù)，每行有三個(gè)正整數(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 |
【評(píng)分標(biāo)準(zhǔn)】
對(duì)于每個(gè)測(cè)試點(diǎn)，如果你能夠在1S內(nèi)通過(guò)每組數(shù)據(jù)，你將得到這個(gè)測(cè)試點(diǎn)的分?jǐn)?shù)，否則，這個(gè)測(cè)試點(diǎn)你只能得0分。
【分析】
原題目是要求輸出一種可能的解，如果沒(méi)有解就輸出-1。這樣的話就要用到差分約束。
現(xiàn)在的話，只需要一個(gè)公式。如果有解，應(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: