当前位置:网站首页>Hdu-6025-prime sequence (girls' competition)
Hdu-6025-prime sequence (girls' competition)
2022-07-06 16:03:00 【It's Xiao Zhang, 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]);// Prefix
}
for(int i=n-1;i>=1;i--)
{
c[i]=gcd(c[i+1],a[i]);// suffix
}
for(int i=1;i<=n;i++)
{
ans=max(ans,gcd(c[i+1],b[i-1]));
}// Every time you remove the i The greatest common divisor after the number
printf("%d\n",ans);
}
return 0;
}
边栏推荐
- F - Birthday Cake(山东省赛)
- Find 3-friendly Integers
- Penetration test (2) -- penetration test system, target, GoogleHacking, Kali tool
- 通俗地理解什么是编程语言
- Cost accounting [19]
- 【练习-10】 Unread Messages(未读消息)
- PySide6 信号、槽
- STM32 learning record: LED light flashes (register version)
- Essai de pénétration (1) - - outils nécessaires, navigation
- HDU - 6024 Building Shops(女生赛)
猜你喜欢
快速转 TypeScript 指南
Penetration test (7) -- vulnerability scanning tool Nessus
Analysis of protobuf format of real-time barrage and historical barrage at station B
Information security - Epic vulnerability log4j vulnerability mechanism and preventive measures
渗透测试 ( 1 ) --- 必备 工具、导航
入门C语言基础问答
STM32 learning record: LED light flashes (register version)
Optimization method of path problem before dynamic planning
Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
Nodejs+vue online fresh flower shop sales information system express+mysql
随机推荐
China earth moving machinery market trend report, technical dynamic innovation and market forecast
Matlab comprehensive exercise: application in signal and system
【练习-3】(Uva 442)Matrix Chain Multiplication(矩阵链乘)
Perform general operations on iptables
Information security - threat detection - Flink broadcast stream broadcaststate dual stream merging application in filtering security logs
对iptables进行常规操作
China potato slicer market trend report, technical dynamic innovation and market forecast
E. Breaking the Wall
Shell Scripting
nodejs爬虫
【练习-4】(Uva 11988)Broken Keyboard(破损的键盘) ==(链表)
[exercise-7] crossover answers
Information security - security professional name | CVE | rce | POC | Vul | 0day
China's earthwork equipment market trend report, technical dynamic innovation and market forecast
渗透测试 ( 5 ) --- 扫描之王 nmap、渗透测试工具实战技巧合集
Pyside6 signal, slot
JS调用摄像头
Opencv learning log 12 binarization of Otsu method
Nodejs+vue网上鲜花店销售信息系统express+mysql
信息安全-威胁检测-flink广播流BroadcastState双流合并应用在过滤安全日志