Матч 346, Общие множители (CommonMultiples)

Дивизион 2, Уровень 2; Дивизион 1, Уровень 1

Имеется массив натуральных чисел а и два числа lower и upper. Необходимо найти количество чисел в интервале от lower до upper включительно, являющимися кратными для всех чисел массива а.

Класс: CommonMultiples

Метод: int countCommMult(vector<int> a, int lower, int upper)

Ограничения: a содержит от 1 до 50 чисел, 1 £ a[i] £ 100, 1 £ upper £ 2*10⁹, 1 £ lower £ upper.

Вход. Массив целых чисел a, целые числа lower и upper.

Выход. Количество чисел в интервале от lower до upper включительно, являющимися кратными для всех чисел массива а.

Пример входа

a	lower	upper
{1,2,3}	5	15
{1,2,4,8,16,32,64}	128	128
{1,1,1}	1	2000000000

Пример выхода

2

1

2000000000

РЕШЕНИЕ

наименьшее общее кратное

Для того чтобы число было кратным для всех чисел массива а, необходимо и достаточно, чтобы оно делилось на наименьшее общее кратное всех чисел массива а. Вычислим в переменной d НОК всех чисел массива а. Если в процессе нахождения наименьшего общего кратного d станет большим upper, то искомых чисел не существует и следует вернуть 0. НОК вычисляем через НОД, используя формулу:

a * b = НОД(a, b) * НОК(a, b)

Количество чисел из интервала [lower … upper], делящихся на d, равно

upper / d – (lower – 1) / d

Для избежания переполнения в вычислениях следует воспользоваться 64 битовым целочисленным типом.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

long long gcd(long long a, long long b)

{

return (!b) ? a : gcd(b,a % b);

}

long long lcm(long long a, long long b)

{

return a / gcd(a,b) * b;

}

class CommonMultiples

{

public:

int countCommMult(vector<int> a, int lower, int upper)

{

long long d = a[0], i;

for(i = 1; i < a.size(); i++)

{

d = lcm(d,a[i]);

if (d > upper) return 0;

}

return upper / d - (lower - 1) / d;

}

};