Блог

Дано число n . Как найти количество всех таких разных кортежей?

(i, j, k) где (i*j)%k == 0, где 1<=i<=n, 1<=j<=n, 1<=k<=n в O(n^2) или лучше.

1. Сохранить количество i * j пар в хэш-таблице / карте / массиве
2. Сделайте что-то вроде просеивания, чтобы подсчитать все кратные k в частотном массиве

Пример кода:

 vector<int>freq(n*n 1); //that's just array of n*n 1 zeroes

for(int i=1; i<=n; i  )
for(int j=1; j<=n; j  )
    freq[i*j]  ;

int cnt = 0;
for(int k=1; k<=n; k  )
    for(int j=0; j<=n*n; j =k) //note these loops look like n^3 at first glance yet it's something like n^2 log n (check harmonic number if you're curious why)
    cnt =freq[j];