Cod sursa(job #782832)

Utilizator petrovsoftpetrov adrian petrovsoft Data 30 august 2012 12:43:12
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<iostream.h>
#include<fstream.h>
typedef struct { long x[100000],p; } vector;
bool exista(vector a,long t) {
	bool ok=false;
	for(long i=1;i<=a.p;i++)
		if(a.x[i]==t) { ok=true; break; }
	return ok;
}
vector divizori(long t) {
	vector a; a.p=0;
	for(long i=2;i<=t/2;i++)
		if(t%i==0) {
			a.p++;
			a.x[a.p]=i;
		}
	a.p++; a.x[a.p]=t;
	return a;
}
int main() {
	long n,nr=1;
	ifstream fin("fractii.in");
	fin>>n;
	fin.close();
	for(long i=1;i<=n;i++)
		for(long j=1;j<=n;j++) {
			vector a=divizori(i),b=divizori(j);
			if(a.p<=b.p) {
				long t=1;
				while(t<=a.p and !exista(b,a.x[t])) t++;
				if(t>a.p) nr++;
			} else {
				long t=1;
				while(t<=b.p and !exista(a,b.x[t])) t++;
				if(t>b.p) nr++;
			}
		}
	ofstream fout("fractii.out");
	fout<<nr;
	fout.close();
}