Сайт Богданова Дмитрия Валериевича

Задание №1701/27

Задание

Дан набор из \(N\) натуральных чисел. Необходимо определить количество пар элементов \(\left(a_{i},a_{j}\right)\) этого набора, в которых \(1\leq i<j\leq N\) и произведение элементов кратно 6.

Напишите эффективную по времени и по памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел \(N\) в \(k\) раз время работы программы увеличивается не более чем в \(k\) раз. Программа считается эффективной по памяти, если память, необходимая для хранения переменных программы, не превышает одного килобайта и не увеличивается с ростом \(N\).

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел \(N\) (\(1\leq N\leq10000\)). В каждой из последующих \(N\) строк записано одно натуральное число, не превышающее 1000.

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

	4
	7
	5
	6
	12

Пример выходных данных для приведённого выше примера входных данных:

	5

В приведённом наборе из 4 чисел имеются пять пар \(\left(7,6\right)\), \(\left(5,6\right)\), \(\left(7,12\right)\), \(\left(5,12\right)\), \(\left(6,12\right)\), произведение элементов которых кратно 6.

Решение

Произведение двух чисел кратно 6, если:

  • один из сомножителей кратен 6 (второй может быть любым);
  • ни один из сомножителей не кратен 6, но один из сомножителей кратен 2, а другой кратен 3.

Поэтому программа, вычисляющая количество пар элементов \(\left(a_{i},a_{j}\right)\), произведение которых кратно 6 и \(1\leq i<j\leq N\), может работать следующим образом. Программа читает все входные данные один раз, не запоминая данные в массиве. Для прочитанного фрагмента входной последовательности в программе хранятся значения трёх величин:

  • \(M_{2}\) — количество чисел, кратных 2, но не кратных 6;
  • \(M_{3}\) — количество чисел, кратных 3, но не кратных 6;
  • \(M_{6}\) — количество чисел, кратных 6.

Первый из элементов, кратных 6, может быть умножен на любой из других \(N-1\) элементов (все элементы последовательности, не включая его самого). Следующий элемент, кратный 6, может быть умножен только на любой из \(N-2\) элементов (так как пара с первым элементом, кратным 6, уже была учтена). Рассуждая аналогично, получим, что количество пар, одним из элементов которой является элемент, кратный 6, равно: \[\left(N-1\right)+\left(N-2\right)+\ldots+\left(N-M_{6}\right)=M_{6}\cdot N-\left(1+2+\ldots+M_{6}\right).\]

Множество пар, в которых один из элементов кратен 2, а второй кратен 3, и при этом оба элемента не кратны 6, не пересекается с рассмотренным выше множеством пар, в которых один из элементов кратен 6. Количество таких пар равно \(M_{2}\cdot M_{3}\).

Отметим, что сумма арифметической прогрессии \(1+2+\ldots+M_{6}\) равна \(M_{6}\cdot\left(M_{6}+1\right)/2\). После того как все данные прочитаны, требуемый в условии ответ вычисляется по формуле: \[M_{6}\cdot N-M_{6}\cdot\left(M_{6}+1\right)/2+M_{2}\cdot M_{3}.\]

Подробнее...

Замечание

Подробнее...

Ответ

Копировать
var
  N, x, i, m2, m3, m6 : integer;
begin
  m2 := 0; m3 := 0; m6 := 0;
  readln(N);
  for i := 1 to N do begin
    readln(x);
    if x mod 6 = 0 then
      m6 := m6 + 1
    else begin
      if x mod 2 = 0 then
        m2 := m2 + 1;
      if x mod 3 = 0 then
        m3 := m3 + 1
    end
  end;
  write(m6 * N + m2 * m3 - m6 * (m6 + 1) div 2)
end.

Подробнее...
Добавить комментарий
Комментарии (4)