fork download
  1. #include <cmath>
  2. #include <vector>
  3. #include <iostream>
  4. #include <unordered_map>
  5.  
  6. std::unordered_map<int, int> build_lookup_table(const std::vector<int>& vec){
  7. std::unordered_map<int, int> table(vec.size());
  8. for(std::size_t row = 0; row < vec.size(); row++)
  9. for(std::size_t col = row + 1; col < vec.size(); col++)
  10. ++table[vec[row] * vec[col]];
  11. return table;
  12. }
  13.  
  14. std::vector<int> get_factors(const int k){
  15. std::vector<int> vec;
  16. const int limit = std::sqrt(k);
  17. for(int i = 1; i <= limit; i++){
  18. int val = k / i;
  19. if(val * i == k)
  20. vec.push_back(i), vec.push_back(val);
  21. }
  22. if(limit * limit == k) //if its a perfect square
  23. vec.pop_back();
  24. return vec;
  25. }
  26.  
  27.  
  28. int main(){
  29. std::vector<int> A;
  30. std::vector<int> Q;
  31. std::vector<int> ans;
  32.  
  33. int n;
  34. std::cin >> n;
  35. for(int i = 0, k; i < n; i++) std::cin >> k, A.push_back(k);
  36.  
  37. std::cin >> n;
  38. for(int i = 0, k; i < n; i++) std::cin >> k, Q.push_back(k);
  39.  
  40. const auto lookup_table = build_lookup_table(A);
  41. for(auto k : Q){
  42. int pairs = 0;
  43. for(auto factor : get_factors(k)){
  44. auto iter = lookup_table.find(factor);
  45. pairs += iter != lookup_table.end() ? iter->second : 0;
  46. }
  47. ans.push_back(pairs);
  48. }
  49. for(auto x : ans)
  50. std::cout << x << ' ';
  51. std::cout << std::endl;
  52. }
Success #stdin #stdout 0s 3476KB
stdin
5
2 5 6 2 3
5
12
20
7
10
200
stdout
5 3 0 2 3