Pagini recente » Cod sursa (job #306113) | Cod sursa (job #1992982) | Cod sursa (job #386180) | Cod sursa (job #624201) | Cod sursa (job #1710160)
#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;
}