Cod sursa(job #2460668)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 24 septembrie 2019 09:16:23
Problema Pairs Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("pairs.in");
ofstream g("pairs.out");
int n, i, j, k = 0, aux, cate = 0, aux1, aux2, aux3;
bool x[1000001];

int main()
{
    f >> n;
    int v[n+1];

    /// Eratostene pana la 1.000.000
    for(i = 2; i*i <= 1000000; i++)
        if(x[i] == 0)
        for(j = 2; i*j <= 1000000; j++)
            x[i*j] = 1;

    for(i = 1; i <= n; i++) {
        f >> v[i];
    }

    /// Sortarea vectorului
    for(i = 1; i < n; i++)
        for(j = i+1; j <= n; j++)
            if(v[i] > v[j]){
                aux = v[i];
                v[i] = v[j];
                v[j] = aux;
            }

    /// Gasirea perechilor
    for(i = 1; i < n; i++) {
        if(x[v[i]] == 0) {
            for(j = i+1; j <= n; j++) {
                if(v[i] < v[j]) {
                if(v[j]%v[i] != 0)
                    k++;
                } else k++;
            }
        } else {
            for(j = i+1; j <= n; j++) {
                if(x[v[j]] == 0)
                    k++;
                else if(!(v[i]%2 ==0 && v[j]%2==0) && !(v[i]%3 ==0 && v[j]%3==0) && !(v[i]%5 ==0 && v[j]%5==0) && !(v[i]%7 ==0 && v[j]%7==0)){
                    aux1 = v[i];
                    aux2 = v[j];
                    while (aux2) {
                        aux3 = aux1 % aux2;
                        aux1 = aux2;
                        aux2 = aux3;
                    }
                    if(aux1 == 1)
                        k++;
                }
            }
        }
    }

    g << k;
    return 0;
}