Задание №1701/27

Произведение двух чисел кратно 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.