1031 Cmmmc

[•stef2n]

Aici puteti discuta despre problema Cmmmc.

[•vladtarniceru]

imi spune si mie va rog cineva care e complexitatea de 100 de puncte la aceasta problema?

[•ssergiuss]

Complexitatea de timp este aproximativ O(K * (sqrtN + 2 ^ (nrdivizoriN))). Ar mai fii pregenerarea numerelor prime pentru care nu stiu exact complexitatea, dar oricum se incadreaza lejer in timp daca faci cu ciurul lui eratostene.

[•S7012MY]

ce inseamna Killed by signal 6(SIGABRT).   ?
ce sa fac sa nu depasesc memoria? lucrez cu vectori din stl.   

[•SpiderMan]

Lucrezi cumva cu assert? De obicei acel semnal il iei daca programul iasa fortat .

[•S7012MY]

Nu lucrez cu assert, dar nu stiu cum sa fac sa mearga problema. Solutia si sursa oficiala nu le prea inteleg si la rez. mea iau erori urate

[•SpiderMan]

Trimite-mi sursa prin PM .

[•romircea2010]

Imi puteti explica si mie cam de ce as putea lua "Killed by signal 8(SIGFPE)"?
Am citit ca e posibil ca acest semnal sa apara pentru ca am o impartire la 0 dar nu am.

[•SpiderMan]

Trimite-mi sursa prin P.M. ca sa pot sa vad de ce iei acea eroare, sunt multiple cazurile.

[•romircea2010]

mersi mult, am rezolvat intre timp
aveam totusi o impartire la 0, mai exact aveam pentru ciur un vector declarat global cu cateva pozitii in plus decat cate aveam nevoie si ajungea acolo.

[•valentin.harsan]

se poate uita cineva pe sirsa mea?  nu reusesc sa vad ce e gresit 
am luat testele de la olimpiada si par sa mearga. nu vad vreo diferenta dar totusi iau 40 pe infoarena.

Cod:

#include<iostream>
#include<fstream>
#define N 500000
using namespace std;

ifstream in("cmmmc.in");
ofstream out("cmmmc.out");

int solmin=100000,sol1,sol2,nrp[144000],nr,fact[400],pu[400],n,sol[400];
bool z[N];

void erat() {
	int i,j;
	
	for(i=2;i*i<N;++i) {
		if(!z[i]) {
			nrp[++nr]=i;
			for(j=2*i;j<N;j+=i)
				z[j]=true;
		}
	}
	
	for(;i<N;++i)
		if(!z[i])
			nrp[++nr]=i;
}

void ver() {
	
	int i,nu1=1,nu2=1;
	
	for(i=1;i<=n;++i) {
		if(sol[i]==0)
			nu1*=fact[i];
		else
			nu2*=fact[i];
	}
	
	if(nu1+nu2<solmin) {
		solmin=nu1+nu2;
		sol1=nu1; sol2=nu2;
		if(sol1>sol2)
			swap(sol1,sol2);
	}
}

void back(int q) {
	
	int i;
	
	if(q==n+1) {
		ver();
		return;
	}
	
	for(i=0;i!=2;++i) {
		sol[q]=i;
		back(q+1);
	}
}

int cmmmc(int p) {
	
	int i,nrr=1;
	
	n=0; solmin=100000;
	
	for(i=1;i<=nr;++i) {
		if(p%nrp[i]==0) {
			fact[++n]=1;
			pu[n]=0;
			while(p%nrp[i]==0) {
				p/=nrp[i];
				++pu[n]; fact[n]*=nrp[i];
			}
			nrr*=(2*pu[n]+1);
		}
	}
	
	if(p!=1) {
		fact[++n]=p;
		pu[n]=1;
		nrr*=3;
	}		
	
	nrr=(nrr+1)>>1;
	
	back(1);
	
	return nrr;
	
}

int main() {
	
	int i,ni,k;
	
	erat();
	
	in >> k;
	
	for(i=1;i<=k;++i) {
		in >> ni;
		
		out << cmmmc(ni) << " " << sol1 << " " << sol2 << "\n";
	}
	
	return 0;
}

[•Magnus]

pare ca pe prima linie din fisierul de iesire la tine ambele numere sunt 0

pe exemplu iti da:

Cod:

5 0 0
2 2 5

inlocuieste afisarea cu

Cod:

out << cmmmc(ni) << " ";
out <<sol1<<" "<<sol2<<"\n";

merge de 70 asa, mai vezi si tu dupa
succes

[•valentin.harsan]

multumesc pentru sfat 
sti ce problema putea avea afisarea? ca la mine dadea bine si se vedea si prima linie

[•Magnus]

cred ca ai o versiune mai veche de compilator

ideea e ca sol1 si sol2 erau modificate dupa afisare

p.s.:compilatorul modifica pe toate linile nu numai pe prima, dar mie imi sarisera in ochi numai zerourile