Можно ли так отнимать так индексы?

Question

На вход программы поступает последовательность из N целых положительных чисел. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре неважен). Необходимо определить количество произвольных пар, произведение чисел и разность индексов которых кратна 3. Описание входных и выходных данных В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 10000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10000. В качестве результата программа должна вывести одно число: количество найденных пар. Пример входных данных №1: 10 1 2 3 4 5 6 7 8 9 10 Выходные данных для приведенного выше примера: 3

var
a: array[1..10000] of integer;
N, i, j, x, b: integer;

begin
x := 0;
readln(N);
for i := 1 to N do
readln(a[i]);
for i := 1 to N - 1 do
for j := i + 1 to N do
  if ((a[i] * a[j]) mod 3 = 0) and ((i - j) mod 3 = 0) then
    x := x + 1;
writeln(x);
end.

Можно ли так отнимать индексы? ((i - j) mod 3 = 0) Это рабочий способ? Или есть какой-то более универсальный?

Answer 1

Да, это рабочий способ.

Более оптимально же будет не проверять все разности индексов, а пройти только по нужным индексам с шагом 3

for i := 1 to N - 1 do
j := i + 3;
while i <= N do begin
   if ((a[i] * a[j]) mod 3 = 0) then
     x := x + 1;
   inc(j, 3);
end;

Answer 2

Задачу можно решить в один проход за O(n) действий, что для n=10000 скорее необходимость, чем прихоть.

Тройка - простое число, чтобы произведение целых чисел делилось на него, необходимо и достаточно, чтобы один из сомножителей делился. Получается следующий алгоритм

Для каждого индекса i ведем подсчет предшествующих чисел с индексами j ≡ i (mod 3)
- только тех, что делятся на 3 (A_i)
- всех таких чисел (B_i)
Если текущее число делится на 3
- прибавляем к результату B_i
- иначе прибавляем A_i

var
  count : array [0..2] of integer;
  x, i, n, result: integer;

begin
  result := 0;
  read(n);

  for i := 0 to n - 1 do
  begin
     read(x);
     
     if x mod 3 = 0 then
     begin
       inc(count[i mod 3]);
       inc(result, i div 3)
     end
     else
     begin
       inc(result, count[i mod 3])
     end;
  end;
  
  writeln(result);
end.

БЛОГ НА HUSL

Можно ли так отнимать так индексы?

Ответы (2 шт):