Решение задачи "Общие делители" с Codeforces

Без пояснения   Просмотров: 10

Вам задан массив a, состоящий из n целых чисел.

Ваша задача — найти количество таких положительных целых чисел x, что x делит каждое число в массиве. Другими словами, вам необходимо найти количество общих делителей всех элементов массива.

Например, если массив a будет равен [2,4,6,2,10], то 1 и 2 делят каждое число в массиве (таким образом, ответ на этот тест равен 2).

Код 

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int n;
	long long g=0;
	cin >> n;
	while(n--)
	{
		long long x;
		cin >> x;
		g=__gcd(g,x);
	}
	int ans=0;
	for(long long i=1;i*i<=g;i++)
	{
		if(g%i==0)
		{
			ans++;
			if(g/i!=i) ans++;
		}
	}
	cout << ans << endl;
}

         

Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться