/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は N 個の宝石を持っています。宝石には 1 から N までの番号が付いており、宝石 i の品質値は A_i です。
高橋君はこの中から 2 個以上の宝石を選んでネックレスを作ろうとしています。ネックレスの「美しさ」は、選んだ宝石すべての品質値の最大公約数（GCD）で定義されます。美しさは選んだ宝石の集合のみで決まり、宝石の並べ方には依存しません。
高橋君は、まず美しさを最大化したいと考えています。さらに、美しさが最大となる選び方が複数存在する場合は、その中で選ぶ宝石の個数が最小のものを選びたいと考えています（余った宝石は他の用途に回せるためです）。
より正確に述べます。宝石の番号の集合 \{1, 2, \ldots, N\} の部分集合のうち、要素数が 2 以上であるものを考え、以下のように値 G と K を定めます。
- そのような部分集合 S すべてについて、S に含まれる各宝石の品質値の GCD、すなわち \gcd(A_i \mid i \in S) を考える。この GCD の最大値を G とする。
- GCD が G に等しい部分集合 S の中で、S の要素数の最小値を K とする。
ネックレスに使わなかった宝石の個数、すなわち N - K を求めてください。
制約
- 2 \leq N \leq 10^6
- 1 \leq A_i \leq 10^6（1 \leq i \leq N）
- 入力は全て整数である。
入力
N A_1 A_2 \ldots A_N
- 1 行目には、宝石の個数を表す整数 N が与えられる。
- 2 行目には、各宝石の品質値を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
出力
ネックレスに使わなかった宝石の個数 N - K を 1 行で出力せよ。
入力例 1
4 6 10 15 21
出力例 1
2
入力例 2
5 7 11 13 17 19
出力例 2
3
入力例 3
12 18 24 30 42 70 105 140 210 35 49 63 77
出力例 3
10
入力例 4
30 360 720 1080 1440 1800 210 330 462 770 1001 1430 2210 2730 3570 4290 6006 8190 9009 12345 23456 34567 45678 56789 67890 78901 89012 99991 999983 500000 1000000
出力例 4
28
入力例 5
2 1 1000000
出力例 5
0
Score : 366 pts
Problem Statement
Takahashi has N gems. The gems are numbered from 1 to N, and gem i has a quality value of A_i.
Takahashi wants to select 2 or more gems from these to make a necklace. The "beauty" of the necklace is defined as the greatest common divisor (GCD) of the quality values of all selected gems. The beauty depends only on the set of selected gems and does not depend on how they are arranged.
Takahashi first wants to maximize the beauty. Furthermore, if there are multiple ways to select gems that achieve the maximum beauty, he wants to choose the one with the minimum number of gems selected (since the remaining gems can be used for other purposes).
More precisely, consider subsets of the set of gem numbers \{1, 2, \ldots, N\} that have at least 2 elements, and define values G and K as follows:
- For all such subsets S, consider the GCD of the quality values of the gems in S, i.e., \gcd(A_i \mid i \in S). Let G be the maximum value of this GCD.
- Among the subsets S whose GCD equals G, let K be the minimum number of elements in S.
Find the number of gems not used in the necklace, i.e., N - K.
Constraints
- 2 \leq N \leq 10^6
- 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
- All inputs are integers.
Input
N A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of gems.
- The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the quality values of each gem.
Output
Print the number of gems not used in the necklace, N - K, in one line.
Sample Input 1
4 6 10 15 21
Sample Output 1
2
Sample Input 2
5 7 11 13 17 19
Sample Output 2
3
Sample Input 3
12 18 24 30 42 70 105 140 210 35 49 63 77
Sample Output 3
10
Sample Input 4
30 360 720 1080 1440 1800 210 330 462 770 1001 1430 2210 2730 3570 4290 6006 8190 9009 12345 23456 34567 45678 56789 67890 78901 89012 99991 999983 500000 1000000
Sample Output 4
28
Sample Input 5
2 1 1000000
Sample Output 5
0