HDU 5223 GCD

题意：给出一列数a,给出m个区间，再给出每个区间的最小公倍数还原这列数

因为数组中的每个数至少都为1，而且一定是这个区间的最小公约数ans[i]的倍数，求出它与ans[i]的最小公倍数，如果大于1e9（题目中给的范围，一定不能够还原）

最后按照这样算出每一个a[i]后，再检查一遍这m个区间的算出来的最小公约数是否和给出的一致

学习的dzy4939414644的代码

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 using namespace std;
12 
13 #define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)
14 
15 typedef long long LL;
16 const int INF = (1<<30)-1;
17 const int mod=1000000007;
18 const int maxn=100005;
19 int n,m;
20 
21 struct node{
22     int l,r,x;
23 } ans[maxn];
24 
25 int a[maxn];
26 
27 LL gcd(LL a,LL b){
28     return (!b)? a:gcd(b,a%b);
29 }
30 
31 LL lcm(LL a,LL b){
32     return a/gcd(a,b)*b;
33 }
34 
35 void solve(){
36     for(int i=1;i<=n;i++) a[i]=1;
37     
38     for(int i=1;i<=m;i++){
39         for(int j=ans[i].l;j<=ans[i].r;j++){
40             a[j]=lcm(a[j],ans[i].x);
41             if(a[j]>1000000000){
42                 printf("Stupid BrotherK!
");
43                 return;
44             }
45         }
46     }
47     
48     for(int i=1;i<=m;i++){
49         LL cur=0;
50         for(int j=ans[i].l;j<=ans[i].r;j++){
51             cur=gcd(a[j],cur);
52         }
53         if(cur!=ans[i].x){
54             printf("Stupid BrotherK!
");
55             return;        
56         }        
57     }
58     
59     printf("%d",a[1]);
60     for(int i=2;i<=n;i++) printf(" %d",a[i]);
61     printf("
");
62 }
63 
64 int main(){
65     int T;
66     scanf("%d",&T);
67     while(T--){
68         scanf("%d %d",&n,&m);
69         for(int i=1;i<=m;i++) scanf("%d %d %d",&ans[i].l,&ans[i].r,&ans[i].x);
70         
71         solve();    
72     }
73     return 0;
74 }

View Code