#2348. 重排

重排

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

t\red{t}每次给定一个长度为n\red{n}的序列a\red{a}。定义数对(i,j)\red{(i,j)}是优美的当且仅当1<=i<j<=n,gcd(ai,2×aj)>1\red{1<=i <j<=n,gcd(a_i,2\times a_j)>1} 。请求出将原序列重排后可以产生的优美数对个数的最大值。

输入格式

第一行一个整数n\red{n,}表示序列长度。

接下来一行n\red{n}个整数ai\red{a_i,}表示序列。

输出格式

输出一行一个整数,表示答案。

样例

输入样例1

4
3 6 5 3

输出样例1

4

输入样例2

5
1 4 2 4 1

输出样例2

9

提示

对于50%\red{50\%}的数据,有1<=n<=20\red{1<=n<=20}

对于100%\red{100\%}的数据,有1<=n<=2000,1<=ai<=105\red{1<=n<=2000,1<=a_i<=10^5}

2024年CSP-J模拟测试3

未参加
状态
已结束
规则
IOI
题目
5
开始于
2024-7-30 20:00
结束于
2024-8-2 8:00
持续时间
60 小时
主持人
参赛人数
43