Unless I'm missing a constraint, I don't see why you need gcd: you just need to know whether each index is divisible by k (maybe confused with sum instead of product?)

A divisible number multiplied by anything is still divisible. A nondivisible must be multiplied by a divisible to be divisible.

[12,5,7,16,9,8,4] k =4

[ T,F,F,F, T,F,T,T]

Run through - if true, count += n-index (all remaining j>i), else += all remaining multiples

N=8

multiples=4

i=0 (true)

Count+=6, multiples--, multiples= 3

i=1 (false)

Count += 3

i=2 (false)

Count += 3

i=4 (true)

Count += 3, multiples--, multiples= 2

i=5 (false)

Count += 2

i=4 (true)

Count += 1, multiples--, multiples= 1

Count =22

Solvable in two n passes