寒光博客

[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 有空继续写,,,

本文作者:Author:     文章标题: [CF]#579 D3 C. Common Divisors
本文地址:https://dxoca.cn/Algorithm/252.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 14th, 2019 at 01:06 am
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment