找到对i和j的对数，使得A [i]和A [j]的乘积有效地划分K.

Question

假设数组A中有整数列表。 给定另一个包含查询的数组Q. 对于每个查询K，您需要找到对i和j的对数，使得A [i]和A [j]的乘积除以K.

如何在没有任何暴力方法的情况下有效地完成这项工作？

例如 ：

特定 答：2 5 6 2 3 问：12 7 100 200 输出：5 0 2 3

说明： 除以12的对的数量是：（1,3），（1,4），（1,5），（3,4），（4,5） 除以7的对数是：无（0）等等......

如何在没有任何暴力方法的情况下有效地完成这项工作？

Answer 1

将所有因素归结为素数的幂。

对于每个查询值，构建N维数组，其中N是查询值的主要因子。每个维度都有k + 1个条目，其中k是相应素数的幂。

绘制此数组中的每个潜在因子，将其位置递增1.如果在数组外部，则丢弃。

使用n维扫描将cdf存储在每个维度的每个维度中。总共少于40个条目，所以这应该足够快。

求和每个潜在因子的“反向”位置。我J和I J无效，通过加倍素数并减去一次来手动检查。

您可以预先计算每个目标或每个源，并构建一个巨大的阵列。但这可能太过分了。

Answer 2

只需快速拍摄：

你可以»预编译«所有可能的S的结果列表A[i] * A[j]并过滤该列表的双打这样的;

A = [1,2,3];
Q = [3,4,5]

All possible results:

1 * [2,3] => 2,3
2 * [1,3] => 2,6
3 * [1,2] => 3,6 //these are 6 values to test for each

S = [2,3,6] //here are only three unique

Than:

2/2, 2/3, 2/6 => 1
3/2, 3/3, 3/6 => 1
6/2, 6/3, 6/6 => 3

Answer 3

A可能会做：

1. 创建一个哈希映射，H包含产品A [i]和A [j]乘以集合A的乘积。（如果您愿意，可以使用2D数组）。
2. 设零初始化m为K中的对数。然后对于K的每个因子，在H中找到它。如果在那里，则通过1增加m。

运行时间：O(N * N) + c * Q。其中N是阵列A的大小; c是查询值的平均因子数; Q是查询数量。

在C ++中：

#include <cmath>
#include <vector>
#include <iostream>
#include <unordered_map>

//returns a hashmap, containing all allowed pairs in vec
std::unordered_map<int, int> build_lookup_table(const std::vector<int>& vec){
    std::unordered_map<int, int> table(vec.size());
    for(std::size_t row = 0; row < vec.size(); row++)
        for(std::size_t col = row + 1; col < vec.size(); col++)
            ++table[vec[row] * vec[col]];
    return table;
}

//a fairly fast and simple way to quickly get factors without using % modulus
std::vector<int> get_factors(const int k){
    std::vector<int> vec;
    const int limit = std::sqrt(k);
    for(int i = 1; i <= limit; i++){
        int val = k / i;
        if(val * i == k)
            vec.push_back(i), vec.push_back(val);
    }
    if(limit * limit == k)      //if its a perfect square
        vec.pop_back();
    return vec;
}


int main(){
    std::vector<int> A{ 2, 5, 6, 2, 3 };
    std::vector<int> Q{12, 20, 7, 10, 200 };
    std::vector<int> ans(Q.size());

    const auto lookup_table = build_lookup_table(A);
    for(auto k : Q){
        auto pairs = 0;
        for(auto factor : get_factors(k)){
            auto iter = lookup_table.find(factor);
            pairs += iter != lookup_table.end() ? iter->second : 0;
        }
        ans.push_back(pairs);
    }

    for(auto x : ans)
        std::cout << x << ' ';
    std::cout << std::endl;
}

See a Demo