Cod sursa(job #32190)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 17 martie 2007 14:22:38
Problema Pascal Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <cstdio>
#include <cmath>
#define FIN "pascal.in"
#define FOUT "pascal.out"

long Nr;
long prim[3] = {2,3,5};
long Exp[][3] = { {0,0,0}, {0,0,0}, {1,0,0}, {0,1,0}, {2,0,0}, {0,0,1}, {1,1,0} };
long P, D;
long numar, ok;
long nr[3], x[3];

inline long f(long x, long y) {
	long ret = 0;
	long p = y;
	for (; p<=x; p*=y) 
		ret += x/p;
	return ret;
}

void pre() {
	long i,j;
	freopen("p.txt", "w", stdout);
	for (i=0; i<2500000; ++i) {
		printf("{");
		for (j=0; j<3; ++j) {
			printf("%ld",f(i,prim[j]));
			if ( j<2 ) 
				printf(",");
		}
		printf("},");
	}
	fclose(stdout);
}

long mp, dp, fp;

void solve1(long i, long j) {
	if ( x[j] ) {
		nr[j] = x[j] - f(P-i, prim[j]) - f(i, prim[j]);
//		nr[j] -= floor(log(P-i) / log(prim[j])) + floor(log(i) / log(prim[j]));
		if ( nr[j] < Exp[D][j] )
			ok = 0;
	}
}

long fact[3][5000001];

long putere(long x, long y) {
	long nr = 0;
	for (; x%y == 0; x/=y)
		nr ++;
	return nr;
}

void pre_solve2() {
	long i,j;
	for (j=0; j<3; ++j)
		for (i=1; i<=P; ++i)
			fact[j][i] = fact[j][i-1] + putere(i,prim[j]);
}

void solve2(long i) { 
	long j;
	for (j=0, ok=1; j<3 && ok; ++j)
		if ( fact[j][P] - fact[j][i] - fact[j][P-i] < Exp[D][j] )
			ok = 0;
}

void debug() {
	long i,j;
	for (j=0; j<3; ++j) {
		for (i=1; i<=P; ++i)
			printf("%5ld", fact[j][i]);
		printf("\n");
	}
}

int main() {
	long i,j ;
	
	freopen(FIN, "r", stdin);
	scanf("%ld %ld", &P, &D);
	fclose(stdin);
/*
	for (j=0; j<3; ++j) 
		nr[j] = x[j] = f(P,prim[j]);

	mp = 0x3f3f3f;
	for (j=0; j<3; ++j)
		if ( Exp[D][j] && mp > x[j]/Exp[D][j] )
			mp = x[j]/Exp[D][j];
*/

	pre_solve2();
//	debug();
	for (i=1; i<=P/2; ++i) {
/*		for (j=0, ok=1; j<3 && ok; ++j) 
			solve1(i,j);*/
		solve2(i);
		numar += ok;
	}

	numar*=2;
	solve2(P/2);
	if ( (P-1)%2 && ok)
		numar --;
	freopen(FOUT, "w", stdout);
	printf("%ld\n", numar);
	fclose(stdout);
	return 0;
}