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).
Examples Input 5 1 2 3 4 5 Output 1 Input 6 6 90 12 18 30 18 Output 4
数据范围很大，考虑一下全员用long long。。。因为long long 来回wa 整理一下思路：找出所有数的最大公约数，再考虑能被最大公约数整除的数， 对于代码for (long long i = 1; i * i <= g; i++)，设g=6，1对应6，2对应3，所以可以i*i<=g作为判断条件对for (long long i = 1; i <= g; i++)优化
#include<cstdio> #include<vector> #include<algorithm> using namespace std; long long gcd(long long a,long long b){ return b==0?a:gcd(b,a%b); } int main() { long long g; long long cnt=0; int n; scanf("%d",&n); for(long long i=0;i<n;i++) { long long x; scanf("%lld",&x); g=gcd(g,x); } for (long long i = 1; i * i <= g; i++) if (g % i == 0) { cnt++; if (i * i < g) cnt++; } printf("%lld\n",cnt); return 0; }