English · Original
Chinese · Translation
Formal · Original
Bash has set out on a journey to become the greatest Pokemon master. To get his first Pokemon, he went to Professor Zulu's Lab. Since Bash is Professor Zulu's favourite student, Zulu allows him to take as many Pokemon from his lab as he pleases.
But Zulu warns him that a group of _k_ > 1 Pokemon with strengths {_s_1, _s_2, _s_3, ..., _s__k_} tend to fight among each other if _gcd_(_s_1, _s_2, _s_3, ..., _s__k_) = 1 (see notes for _gcd_ definition).
Bash, being smart, does not want his Pokemon to fight among each other. However, he also wants to maximize the number of Pokemon he takes from the lab. Can you help Bash find out the maximum number of Pokemon he can take?
**Note**: A Pokemon cannot fight with itself.
## Input
The input consists of two lines.
The first line contains an integer _n_ (1 ≤ _n_ ≤ 105), the number of Pokemon in the lab.
The next line contains _n_ space separated integers, where the _i_\-th of them denotes _s__i_ (1 ≤ _s__i_ ≤ 105), the strength of the _i_\-th Pokemon.
## Output
Print single integer — the maximum number of Pokemons Bash can take.
[samples]
## Note
_gcd_ (greatest common divisor) of positive integers set {_a_1, _a_2, ..., _a__n_} is the maximum positive integer that divides all the integers {_a_1, _a_2, ..., _a__n_}.
In the first sample, we can take Pokemons with strengths {2, 4} since _gcd_(2, 4) = 2.
In the second sample, we can take Pokemons with strengths {2, 4, 6}, and there is no larger group with _gcd_ ≠ 1.
Bash 出发踏上成为最伟大 Pokemon 掌握者的旅程。为了获得他的第一只 Pokemon，他前往了 Zulu 教授的实验室。由于 Bash 是 Zulu 教授最喜爱的学生，Zulu 允许他从实验室带走任意数量的 Pokemon。
但 Zulu 警告他：如果一组 #cf_span[k > 1] 只 Pokemon 的力量为 #cf_span[{s1, s2, s3, ..., sk}]，且满足 #cf_span[gcd(s1, s2, s3, ..., sk) = 1]（有关 #cf_span[gcd] 的定义请参见注释），则它们会彼此争斗。
Bash 聪明地不希望他的 Pokemon 彼此争斗。然而，他也希望最大化从实验室带走的 Pokemon 数量。你能帮助 Bash 找出他最多能带走多少只 Pokemon 吗？
*注*：一只 Pokemon 不会与自己争斗。
输入包含两行。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105])，表示实验室中 Pokemon 的数量。
第二行包含 #cf_span[n] 个用空格分隔的整数，其中第 #cf_span[i] 个整数表示 #cf_span[si] (#cf_span[1 ≤ si ≤ 105])，即第 #cf_span[i] 只 Pokemon 的力量。
请输出一个整数 —— Bash 最多能带走的 Pokemon 数量。
#cf_span[gcd]（最大公约数）是指正整数集合 #cf_span[{a1, a2, ..., an}] 中能整除所有整数 #cf_span[{a1, a2, ..., an}] 的最大正整数。
在第一个样例中，我们可以选择力量为 #cf_span[{2, 4}] 的 Pokemon，因为 #cf_span[gcd(2, 4) = 2]。
在第二个样例中，我们可以选择力量为 #cf_span[{2, 4, 6}] 的 Pokemon，且不存在更大的集合满足 #cf_span[gcd ≠ 1]。
## Input
输入包含两行。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105])，表示实验室中 Pokemon 的数量。第二行包含 #cf_span[n] 个用空格分隔的整数，其中第 #cf_span[i] 个整数表示 #cf_span[si] (#cf_span[1 ≤ si ≤ 105])，即第 #cf_span[i] 只 Pokemon 的力量。
## Output
请输出一个整数 —— Bash 最多能带走的 Pokemon 数量。
[samples]
## Note
#cf_span[gcd]（最大公约数）是指正整数集合 #cf_span[{a1, a2, ..., an}] 中能整除所有整数 #cf_span[{a1, a2, ..., an}] 的最大正整数。在第一个样例中，我们可以选择力量为 #cf_span[{2, 4}] 的 Pokemon，因为 #cf_span[gcd(2, 4) = 2]。在第二个样例中，我们可以选择力量为 #cf_span[{2, 4, 6}] 的 Pokemon，且不存在更大的集合满足 #cf_span[gcd ≠ 1]。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of Pokemon.
Let $ S = \{s_1, s_2, \dots, s_n\} \subseteq \mathbb{Z}^+ $ be the multiset of Pokemon strengths, where $ 1 \leq s_i \leq 10^5 $.
**Constraints**
$ 1 \leq n \leq 10^5 $
**Objective**
Find the maximum size of a subset $ T \subseteq S $ such that $ \gcd(T) > 1 $.
API Response (JSON)
{
"problem": {
"name": "B. Bash's Big Day",
"description": {
"content": "Bash has set out on a journey to become the greatest Pokemon master. To get his first Pokemon, he went to Professor Zulu's Lab. Since Bash is Professor Zulu's favourite student, Zulu allows him to tak",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF757B"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Bash has set out on a journey to become the greatest Pokemon master. To get his first Pokemon, he went to Professor Zulu's Lab. Since Bash is Professor Zulu's favourite student, Zulu allows him to tak...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Bash 出发踏上成为最伟大 Pokemon 掌握者的旅程。为了获得他的第一只 Pokemon，他前往了 Zulu 教授的实验室。由于 Bash 是 Zulu 教授最喜爱的学生，Zulu 允许他从实验室带走任意数量的 Pokemon。\n\n但 Zulu 警告他：如果一组 #cf_span[k > 1] 只 Pokemon 的力量为 #cf_span[{s1, s2, s3, ..., sk}]，且满...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of Pokemon. \nLet $ S = \\{s_1, s_2, \\dots, s_n\\} \\subseteq \\mathbb{Z}^+ $ be the multiset of Pokemon strengths, where $ 1 \\leq s_i \\leq 10^5 ...",
"is_translate": false,
"language": "Formal"
}
]
}