[CF]#579 D3 C. Common Divisors
Question You are given an array a consisting of n integer...

14
2019/08

# [CF]#579 D3 C. Common Divisors

## Question

You are given an array a consisting of n integers.

Your task is to say the number of such positive integers x such that x divides each number from the array. In other words, you have to find the number of common divisors of all elements in the array.

For example, if the array a will be [2,4,6,2,10], then 1 and 2 divide each number from the array (so the answer for this test is 2).

### Input

The first line of the input contains one integer n (1≤n≤4⋅105) — the number of elements in a.

The second line of the input contains n integers a1,a2,…,an (1≤ai≤1012), where ai is the i-th element of a.

### Output

Print one integer — the number of such positive integers x such that x divides each number from the given array (in other words, the answer is the number of common divisors of all elements in the array).

## 代码

WA

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int count = 0;
long a[] = new long[n];
long min = Long.MAX_VALUE;
for (int i = 0; i < n; i++) {
a[i] = cin.nextInt();
if (a[i] < min) min = a[i];
}
int[] ans = new int[(int) min + 1];
for (int i = 1; i <= min; i++) {
for (int j = 0; j < n; j++) {
if (a[j] % i == 0) {
ans[i]++;
}
}
}
for (int k : ans) {
if (k == n) {
count++;
}
}
System.out.println(count);
}
}

AC 有空继续写，，，

百度已收录

Last modification：August 14th, 2019 at 01:06 am