Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2730
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2730
Paired Pairs
By Marianne Linhares, UFCG 
Brazil
Timelimit: 2
Maria Luisa loves math, she just won two sets of integers: set A and set B, both sets have the same number of elements. She's playing a game where she creates pairs using elements from these sets.
But this game was not so fun as she thought, to make this interesting Maria Luisa defined a concept of a paired pair. A pair is paired if the greatest common divisor of the integers from the pair is 1. For instance: (2, 4) is not a paired pair, but (3, 5) is a paired pair.
Maria Luisa wants your help to know how many paired pairs there are such that one pair is composed of an element of A and an element of B. Two pairs (p1, p2) and (p3, p4) are equal if p1 = p3 and p2 = p4.
Here's a complete example:
A = {3, 2}
B = {2, 5}
The answer is: 6 and all the possible paired pairs are: (3, 2) (2, 3) (3, 5) (5, 3) (2, 5) (5, 2).
Input
The input consists of several lines. The first line contains an integer N (1 ≤ N ≤ 200) representing the number of elements in the sets. The second line contains N positive integers that belong to A and the third line contains N positive integers that belong to B.
N=0 ends the input. All numbers are 32 bits integers.
Output
The number of different paired pairs that can be obtained using a number from A and a number from B.
| Input Sample | Output Sample |
|
5 1 2 3 4 5 2 4 6 8 10 2 3 2 2 5
0 |
26 6 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<iterator>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<stack>
#include<queue>
#include<math.h>
#include <utility>
#include <sstream>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
typedef long long ll;
int gcd(int a, int b) { return (b == 0 ? a : gcd(b, a % b)); }
int main(int argc, char** argv) {
//freopen("c.txt","w",stdout);
int n;
while(cin >> n&&n)
{
vector<int> a(n);
vector<int> b(n);
set < pair < int,int > > st;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < n; i++)
cin >> b[i];
int count=0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(gcd(a[i],b[j]) == 1)
{
st.insert(make_pair(a[i],b[j]));
st.insert(make_pair(b[j],a[i]));
}
}
}
cout << st.size() << endl;
}
return 0;
}
Input
1 2 3 4 5
2 4 6 8 10
2
3 2
2 5
0
Output
6