Cod sursa(job #1710160)

Utilizator cami9719Camelia Hanes cami9719 Data 28 mai 2016 16:39:55
Problema Consecutive Scor 0
Compilator cpp Status done
Runda Arhiva ICPC Marime 2.59 kb
#include <iostream>
#include <fstream>
#define mx 10000
using namespace std;
ifstream f("consecutive.in");
ofstream g("consecutive.out");

struct mod {
long long p1, p2;
};

//pentru gasirea tuturor cazurilor posibile avem nevoie sa gasim cati diviori primi are numarul pus in discutie si pentru eficientizarea procesului de cautare
//ne folosim de proprietatile ciurului lui Eratosthenes

void ciurul_lui_Eratosthenes ( long long& lungime, long long c[], long long n ){
    long long v[mx];
    lungime = 0;
for ( long long i = 2; i<= n; i++ ){
    v[i] = 0;
}
v[1] = 1; //adica nu e prim
for ( int  i = 2; i<= n; i++ ){
    if ( v[i] == 0 ){
        long long k = 2*i;
        while ( k <= n ){
            v[k] = 1;
            k+=i;
        }
    }
}
for ( int i = 0; i< n; i++ ){
    if ( v[i] == 0 ){
        c[lungime] = i;
        lungime ++;
    }
}
}

//in vectorul c sunt stocate toate numerele prime mai mici sau egale cu n (doar numerele prime)

void tiparireSir ( long long lungime, long long sir[] ){
for ( int i = 1; i< lungime; i++ ){
    cout << sir[i] <<" ";
}
}

void determinaNumereCnsecutive_cu_suma_N ( long long N, long long& nrVariante, mod MNR[ ], long long c[ ], long long lgc){
    nrVariante = 0;
if ( N % 2 == 1 ){
    MNR[nrVariante].p1 = N / 2;
    MNR[nrVariante].p2 = N / 2 + 1;
    nrVariante ++;
}
for ( long long  i = 2; i< lgc && N/c[i] >=0 ; i++ ){
    if( N % c[i] == 0) {
        long long k = N/c[i]; // este divizibil cu numarul prim considerat;
        //c[i] este totodata si numarul de termeni din suma, iar suma e alcatuita din n/k  cu termeni la stanga si la reapta in numar egal
        long long st, dr;
        st = k - (c[i]/2); //termenul cel mai din stanga
        dr = k + (c[i]/2); //numarul de unitati necesare la dreapta pentru a rezulta numarul din partea superioara, cel mi mare
        MNR[nrVariante].p1 = st;
        MNR[nrVariante].p2 = dr;
        nrVariante ++;
    }
}
}

int main()
{
    long long C[mx], lungime, N, maxx;
    maxx= mx;
    ciurul_lui_Eratosthenes(lungime, C, maxx);
    //s-a creat sirul numerelor prime pana la mx;
    long long T; //numarul de teste
    f >> T;
    for ( int i = 1; i<= T; i++ ){
        f >> N; //pe fiecare linie e numarul natural N;
        mod MNR[mx];
        long long nrVariante;
        determinaNumereCnsecutive_cu_suma_N(N, nrVariante, MNR, C, lungime);
        g << nrVariante <<"\n";
        for ( int q = 0; q<nrVariante; q++ ){
            g << MNR[q].p1 <<" "<< MNR[q].p2 <<"\n";
        }
    }
    f.close();
    g.close();
    return 0;
}