Find count of all such distinct tuples, (i, j, k) where (i*j)%k == 0

Question

Given a number n. How to find the count of all such distinct tuples?

(i, j, k) where (i*j)%k == 0, where 1<=i<=n, 1<=j<=n, 1<=k<=n in O(n^2) or better.

Answer 1

1. Store counts of i*j pairs in hashtable/map/array
2. Do something like sieve to count all multiples of k in frequency array

Sample code:

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];