Найти количество всех таких различных наборов, (i, j, k), где (i * j)% k == 0

Question

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

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

Answer 1

1. Сохранение количества пар i * j в хеш-таблице / карте / массиве
2. Сделайте что-то вроде sieve для подсчета всех кратных 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];