当前位置:网站首页>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;
}
边栏推荐
- LeetCode#412. Fizz Buzz
- MATLAB综合练习:信号与系统中的应用
- The most detailed postman interface test tutorial in the whole network. An article meets your needs
- Indonesian medical sensor Industry Research Report - market status analysis and development prospect forecast
- What are the software testing methods? Show you something different
- Cost accounting [18]
- C语言数组的概念
- Research Report on pharmaceutical R & D outsourcing service industry - market status analysis and development prospect forecast
- cs零基础入门学习记录
- 学习记录:如何进行PWM 输出
猜你喜欢
ucorelab3
How to write the bug report of software test?
Crawler series (9): item+pipeline data storage
C4D quick start tutorial - Introduction to software interface
ucore lab7
12306: mom, don't worry about me getting the ticket any more (1)
ucore lab 6
Future trend and planning of software testing industry
学习记录:TIM—电容按键检测
Eslint--- error: newline required at end of file but not found (EOL last) solution
随机推荐
STM32学习记录:输入捕获应用
Eslint--- error: newline required at end of file but not found (EOL last) solution
Learning record: Tim - Basic timer
Winter vacation daily question - maximum number of balloons
编程到底难在哪里?
UCORE LaB6 scheduler experiment report
Perinatal Software Industry Research Report - market status analysis and development prospect forecast
ucore lab7
0-1背包问题(一)
Word macro operation: convert the automatic number in the document into editable text type
学习记录:如何进行PWM 输出
LeetCode#2062. Count vowel substrings in strings
Printing quality inspection and verification system Industry Research Report - market status analysis and development prospect forecast
Introduction to safety testing
Learning record: understand systick system timer and write delay function
力扣刷题记录
[C language] twenty two steps to understand the function stack frame (pressing the stack, passing parameters, returning, bouncing the stack)
入门C语言基础问答
Your wechat nickname may be betraying you
China earth moving machinery market trend report, technical dynamic innovation and market forecast