2017中国大学生程序设计竞赛 Coprime Sequence

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 545 Accepted Submission(s): 190

Problem Description

Do you know what is called ``Coprime Sequence''? That is a sequence consists of

positive integers, and the GCD (Greatest Common Divisor) of them is equal to 1.
``Coprime Sequence'' is easy to find because of its restriction. But we can try to maximize the GCD of these integers by removing exactly one integer. Now given a sequence, please maximize the GCD of its elements.

Input

The first line of the input contains an integer

, denoting the elements in the sequence.

Output

For each test case, print a single line containing a single integer, denoting the maximum GCD.

Sample Input

1 1 1

2 2 2 3 2

1 2 4 8

Sample Output

题意：给出一组数组，他们的最大公约数为1，现在删除一个数，使得最大公约数最大

解法：先知道，只有一种数字和两种数字的情况，后面记录一个数左边的最大公约数，这个数右边的最大公约数（左右都包括它自己），然后l[i-1]和r[i+1]再求一个最大公约数就是删除这个数字的情况

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 set<int>q;
 5 int main()
 6 {
 7     std::ios::sync_with_stdio(false);
 8     int t;
 9     int x[400000];
10     int num;
11     while(cin>>t)
12     {
13         while(t--)
14         {
15             q.clear();
16             int a=0;
17             int b=0;
18             int n;
19             cin>>n;
20             for(int i=1; i<=n; i++)
21             {
22                 cin>>x[i];
23                 if(x[i]%2)
24                 {
25                     a++;
26                 }
27                 else
28                 {
29                     b++;
30                 }
31                 q.insert(x[i]);
32             }
33             if(q.size()==1)
34             {
35                 cout<<x[1]<<endl;
36             }
37             else if(q.size()==2)
38             {
39                 if(x[1]==x[2])
40                 {
41                     cout<<x[1]<<endl;
42                 }
43                 else
44                 {
45                     cout<<x[2]<<endl;
46                 }
47             }
48             else
49             {
50                 int l[400000],r[400000];
51                 l[1]=x[1];
52                 r[n]=x[n];
53                 for(int i=2;i<n;i++)
54                 {
55                     l[i]=__gcd(l[i-1],x[i]);
56                 }
57                 for(int i=n-1;i>=1;i--)
58                 {
59                     r[i]=__gcd(r[i+1],x[i]);
60                 }
61                 int ans=max(l[n-1],r[1]);
62                 for(int i=2;i<n;i++)
63                 {
64                     ans=max(ans,__gcd(l[i-1],r[i+1]));
65                 }
66                 cout<<ans<<endl;
67             }
68         }
69     }
70     return 0;
71 }

2017中国大学生程序设计竞赛 Coprime Sequence

相关推荐