#2348. 重排
重排
题目描述
每次给定一个长度为的序列。定义数对是优美的当且仅当 。请求出将原序列重排后可以产生的优美数对个数的最大值。
输入格式
第一行一个整数表示序列长度。
接下来一行个整数表示序列。
输出格式
输出一行一个整数,表示答案。
样例
输入样例1
4
3 6 5 3
输出样例1
4
输入样例2
5
1 4 2 4 1
输出样例2
9
提示
对于的数据,有;
对于的数据,有。
t每次给定一个长度为n的序列a。定义数对(i,j)是优美的当且仅当1<=i<j<=n,gcd(ai,2×aj)>1 。请求出将原序列重排后可以产生的优美数对个数的最大值。
第一行一个整数n,表示序列长度。
接下来一行n个整数ai,表示序列。
输出一行一个整数,表示答案。
4
3 6 5 3
4
5
1 4 2 4 1
9
对于50%的数据,有1<=n<=20;
对于100%的数据,有1<=n<=2000,1<=ai<=105。