当前位置:网站首页>HDU-6025-Coprime Sequence(女生赛)
HDU-6025-Coprime Sequence(女生赛)
2022-07-06 09:25:00 【是小张张呀 zsy】
Coprime Sequence
Do you know what is called "Coprime Sequence’’? That is a sequence consists of nn 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 T(1≤T≤10),
denoting the number of test cases.
In each test case, there is an integer n(3≤n≤100000) in the first line, denoting the number of integers in the sequence.
Then the following line consists of n integers
a1,a2,…,an (1<=ai<=1e9) 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
3
3
1 1 1
5
2 2 2 3 2
4
1 2 4 8
Sample Output
1
2
2
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int const N=1e5+10;
typedef long long ll;
int a[N],b[N],c[N];
int gcd(ll x,ll y)
{
return y==0?x:gcd(y,x%y);
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
int n,ans=1;
scanf("%d",&n);
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+1+n);
b[1]=a[1];
c[n]=a[n];
for(int i=2;i<=n;i++)
{
b[i]=gcd(b[i-1],a[i]);//前缀
}
for(int i=n-1;i>=1;i--)
{
c[i]=gcd(c[i+1],a[i]);//后缀
}
for(int i=1;i<=n;i++)
{
ans=max(ans,gcd(c[i+1],b[i-1]));
}//每次除去第i个数后的最大公约数
printf("%d\n",ans);
}
return 0;
}
边栏推荐
- TCP的三次握手与四次挥手
- JS --- BOM details of JS (V)
- ucore Lab 1 系统软件启动过程
- Visual analysis of data related to crawling cat's eye essays "sadness flows upstream into a river" | the most moving film of Guo Jingming's five years
- 0-1 knapsack problem (I)
- Report on the market trend, technological innovation and market forecast of printing and decorative paper in China
- C语言是低级和高级的分水岭
- JDBC introduction
- Accounting regulations and professional ethics [2]
- ucore lab7
猜你喜欢
What if software testing is too busy to study?
51 lines of code, self-made TX to MySQL software!
STM32 learning record: input capture application
学习记录:串口通信和遇到的错误解决方法
Matlab example: two expressions of step function
How to build a nail robot that can automatically reply
学习记录:STM32F103 时钟系统概述工作原理
ucore lab 6
学习记录:使用STM32F1看门狗
C语言数组的概念
随机推荐
How to do agile testing in automated testing?
51 lines of code, self-made TX to MySQL software!
Accounting regulations and professional ethics [1]
Research Report on printed circuit board (PCB) connector industry - market status analysis and development prospect forecast
Accounting regulations and professional ethics [2]
China medical check valve market trend report, technical dynamic innovation and market forecast
ucore lab 2
Cost accounting [15]
JS --- detailed explanation of JS facing objects (VI)
JS --- BOM details of JS (V)
Es6---es6 content details
Market trend report, technical innovation and market forecast of Chinese hospital respiratory humidification equipment
JS --- JS function and scope (II)
Learning record: Tim - capacitive key detection
Your wechat nickname may be betraying you
12306: mom, don't worry about me getting the ticket any more (1)
Brief introduction to libevent
Research Report on market supply and demand and strategy of geosynthetics industry in China
China chart recorder market trend report, technology dynamic innovation and market forecast
csapp shell lab