查找所有此类不同元组的计数，(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. 在 hashtable/map/array
中存储 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];