找到所有这些不同元组的计数，（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. 做一些像筛子一样计算频率数组中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];