数学赛码 1010 GCD

 1 /*
 2     数学：官方题解
 3         首先，数组中每个元素至少是1
 4         然后对于任意一个询问Li, Ri, Ansi, 说明Li ~ Ri中的元素必定是Ansi的倍数，那么只需将其与Ansi取最小公倍数即可
 5         如果在计算过程中有一个值超出了可行范围，那么就无解了
 6         在计算完成之后，注意这个解并不一定是正确的，还需要对于所有询问检查一遍
 7         时间复杂度O(NQlogX), X为值的范围
 8     题目不难，算是签到题，可是队友考虑复杂了，GCD (0, ..) ？！
 9     反思：题目要读仔细，组队时做不来要让队友帮忙读题想题
10 */
11 #include <cstdio>
12 #include <iostream>
13 #include <algorithm>
14 #include <cstring>
15 #include <string>
16 #include <map>
17 #include <vector>
18 #include <set>
19 #include <cmath>
20 #include <queue>
21 using namespace std;
22 
23 typedef long long LL;
24 
25 const int MAXN = 1e3 + 10;
26 const int INF = 0x3f3f3f3f;
27 LL a[MAXN];
28 int l[MAXN], r[MAXN];
29 LL ans[MAXN];
30 
31 LL GCD(LL a, LL b)
32 {
33     return b ? GCD (b, a % b) : a;
34 }
35 
36 LL LCM(LL a, LL b)
37 {
38     return a / GCD (a, b) * b;
39 }
40 
41 int main(void)        //赛码 1010 GCD
42 {
43     //freopen ("J.in", "r", stdin);
44 
45     int t, n, q;
46     scanf ("%d", &t);
47     while (t--)
48     {
49         scanf ("%d%d", &n, &q);
50         for (int i=1; i<=n; ++i)    a[i] = 1;
51 
52         bool flag = false;
53         for (int i=1; i<=q; ++i)
54         {
55             scanf ("%d%d%I64d", &l[i], &r[i], &ans[i]);
56             for (int j=l[i]; j<=r[i]; ++j)
57             {
58                 a[j] = LCM (a[j], ans[i]);
59                 if (a[j] > 1e9)
60                 {
61                     flag = true;    break;
62                 }
63             }
64         }
65 
66         if (flag)
67         {
68             puts ("Stupid BrotherK!");    continue;
69         }
70 
71         for (int i=1; i<=q; ++i)
72         {
73             LL k = a[l[i]];
74             for (int j=l[i]+1; j<=r[i]; ++j)
75             {
76                 k = GCD (k, a[j]);
77             }
78             if (k != ans[i])
79             {
80                 flag = true;    puts ("Stupid BrotherK!");    break;
81             }
82         }
83 
84         if (!flag)    for (int i=1; i<=n; ++i)
85             printf ("%I64d%c", a[i], (i==n) ? '
' : ' ');
86     }
87 
88     return 0;
89 }
90 
91 /*
92 Stupid BrotherK!
93 */
编译人生，运行世界！
数学 赛码 1010 GCD

数学赛码 1010 GCD
