fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int multiples(vector<int>&A, vector<int>&B){
  5.     unordered_map<int,int> mppA, mppB;
  6.  
  7.     for(int x : A) mppA[x]++;
  8.     for(int x : B) mppB[x]++;
  9.  
  10.     int maxB = *max_element(B.begin(), B.end());
  11.     long long fin_count = 0;
  12.  
  13.     for(auto it : mppA){
  14.         int current = it.first;
  15.         int freqA = it.second;
  16.  
  17.         if(current == 0) continue;
  18.  
  19.         int count = 0;
  20.         for(int j = current; j <= maxB; j += current){
  21.             if(mppB.count(j))
  22.                 count += mppB[j];
  23.         }
  24.  
  25.         fin_count += 1LL * count * freqA;
  26.     }
  27.  
  28.     return fin_count;
  29. }
  30.  
  31. int main(){
  32.     int n, m;
  33.     cin >> n >> m;
  34.  
  35.     vector<int> A(n), B(m);
  36.  
  37.     for(int i = 0; i < n; i++)
  38.         cin >> A[i];
  39.  
  40.     for(int i = 0; i < m; i++)
  41.         cin >> B[i];
  42.  
  43.     int count = multiples(A, B);
  44.     cout << "Number of valid pairs: " << count << endl;
  45.  
  46.     return 0;
  47. }
  48.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
5 5
1 2 3 4 5
5 10 20 30 50
stdout
copy 
Number of valid pairs: 16
https://ideone.com/7c4qtE
language:
C++ (gcc 8.3)
created:
3 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!