Cerința

Se dau două șiruri de câte N numere fiecare. Se cere să se găsească valoarea maximă a celui mai mare divizor comun a două numere A și B, astfel încât A să aparțină primului șir, iar B să aparțină celui de-al doilea șir.

Date de intrare

În fișierul gcd.in se va afla pe prima linie un număr reprezentând valoarea lui N. Pe cea de-a doua linie se vor afla N numere separate prin câte un spațiu, reprezentând elementele primului șir. Pe cea de-a treia linie se vor afla N numere separate prin câte un spațiu, reprezentând elementele celui de-al doilea șir.

Date de ieșire

În fișierul gcd.out se va afla pe primia linie un număr natural reprezentând valoarea maximă a celui mai mare divizor comun a două numere A și B, astfel încât A să aparțină primului șir, iar B să aparțină celui de-al doilea șir.

Restricții și precizări

• N <= 500.000
• Elementele celor două șiruri <= 1.000.000
• Pentru 40% din teste, N <= 1.000

Exemplu

gcd.in

5
3 1 4 2 8
5 2 12 8 3

gcd.out

8

Explicație

A = 8, B = 8, iar (A,B) = 8 este valoarea maximă a celui mai mare divizor comun a vreunei perechi.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("gcd.in");
ofstream cout("gcd.out");

int n , a[1000001] , b[1000001] , c , maxi , x[1000001] , y[1000001];

int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
    {
        cin >> c;
        a[c]++;
        if(c > maxi) maxi = c;
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        cin >> c;
        b[c]++;
        if(c > maxi) maxi = c;
    }
    for(int i = 1 ; i <= maxi ; ++i)
        for(int j = i ; j <= maxi ; j += i)
        {
            if(a[j] != 0) x[i] = max(x[i] , j);
            if(b[j] != 0) y[i] = max(y[i] , j);
        }
    int ok = 0;
    for(int i = maxi ; i >= 0 ; --i)
        if(x[i]&&y[i]) break;
        else ok++;
    cout << maxi - ok;
    return 0;
}