Нахождение пар кратных чисел. Эффективный алгоритм.

Необходимо найти количество пар, произведение чисел которых кратно 34.

Число 34 можно разложить на 2 простых: 17 и 2.

Нужно подсчитать количество чисел по кратности при вводе:

	var k,k2,k17,N,x: longint;
	begin
	k:=0; k2:=0; k17:=0;
	readln(N);
	for i:=1 to n do
	begin
	readln(x);
	if (x mod 34 = 0) then k:=k+1
	else if (x mod 2 = 0) then k2:=k2+1
	else if (x mod 17 = 0) then k17:=k17+1;
	end;
	end.

view raw Inf.pas hosted with ❤ by GitHub

Формула для нахождения чисел, кратных 34:

k(k-1)/2+k(N-k)+k2*k17,

где k(k-1)/2 - количество пар, где оба сомножителя делятся на 34,
k(N-k) - количество пар, где только один сомножитель делятся на 34,
k2*k17 - количество пар, которые не делятся на 34, но один сомножитель делится на 17, другой на 2.
Формула для нахождения чисел, НЕ кратных 34:

N(N-1)/2-(k(k-1)/2+k(N-k)+k2*k17),

где N(N-1)/2 - общее количество возможных пар.