C. Common Divisors

Problem

You are given an array aa consisting of nn integers.

Your task is to say the number of such positive integers xx such that xx 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 aa will be [2,4,6,2,10][2,4,6,2,10], then 11 and 22 divide each number from the array (so the answer for this test is 22).

Input

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

The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤10121≤ai≤1012), where aiai is the ii-th element of aa.

Output

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

Examples

input

5
1 2 3 4 5

output

1

input

6
6 90 12 18 30 18

output

4

解题思路：

题意（个人理解）：给n个数找最小公倍数的除数（公共因子个数）

例如：
       n=6      a[6]={6 ,90 ,12, 18, 30, 18};
       可求最小公倍数为6

       再求最小公倍数的除数分别有：1,2,3,6

       所以输出4（共有4个除数）

思路：

       首先，先寻找最小公倍数（用到c++内置函数：temp=__gcd(a,b)），再寻找最temp的除数（注意：此处的除数包括1）；这里有个小细节值得注意，若是直接for（i = 0-temp）求除数会超时，那么可以筛选根号temp内的数，sum+=2；

C++提交代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

ll a[400005],n;

int main()
{
    cin >> n;
    ll temp;
    for (int i = 0; i < n; i++) {              //求n的数的最小公倍数
        cin >> a[i];
        if(i == 0)
            temp = a[0];
        else
            temp = __gcd(temp,a[i]);

    }

    ll sum = 0;
    for (ll i = 1; i * i <= temp; i++) {      //求temp的除数个数
        if(temp % i == 0) {
            sum++;
            if(i * i != temp)
                sum++;
        }
    }

    cout << sum;

    return 0;
}

每日一言：

因为努力，今天的你比昨天更强大