Cod sursa(job #33376)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 19 martie 2007 12:07:19
Problema Pascal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <cstdio>
#include <cmath>
#define FIN "chernel.in"
#define FOUT "chernel.out"
#define MAX 100010
#define PRIM_MAX 16000
#define MAXSIZE MAX/16+1


long prim[PRIM_MAX], nr, ans;
long N,M;
char v[MAXSIZE];

void ciur(long n) {
	long i,j;
	for (i=1; ((i*i)<<1) + (i<<1) <= n; i++)
		if ( (v[i>>3] & (1<< (i&7)))==0 )
			for (j=(i*i)<<1+(i<<1); (j<<1) + 1 <=n; j+=(i<<1) + 1)
				v[i>>3] |= (1<<(i&7));
	if ( M%2 ) 
		prim[nr=0] = 2;
	else
		nr=-1;
	for (i=1; (i<<1)+1<=n; ++i)
		if ( ((v[i>>3] & (1<<(i&7))) ==0) && (M%((i<<1)+1)==0) ) {
			prim[++nr] = (i<<1)+1;
		}
}

long putere(long n, long x) { //la ce putere apare x [prim] in descompunerea lui n!
	long lala=0, p=n;
	while (p) 
		lala+= (p/=x);
	return lala;
}

long pute[50][MAX]; // :P

void solve() {
	long i,j,sv=M, pt, ok=0;

	for (j=0; j<=nr; ++j)
		for (i=1; i<=N; ++i)
			pute[j][i]=pute[j][i-1]+putere(i,prim[j]);

	for (j=0; j<=nr && sv>1; ++j)
		for (pute[j][0]=0; sv%prim[j] == 0; pute[j][0]++, sv/=prim[j] );

	for (i=1; i<=N/2; ++i) {
		//elementul i de pe randul N este N!/ [ (N-i)! * i! ]
		ok= 1;
		for (j=0; j<=nr && ok; ++j) {
			pt = pute[prim[j]][2];
//			if ( pt>(putere(N,prim[j])-putere(N-i, prim[j])-putere(i,prim[j])) )
			if ( pt>pute[j][N]-pute[j][i]-pute[j][N-i] )
					ok=0;
		}
		/*
		if ( sv>1 ) 
			if ( putere(N,sv) - putere(N-i,sv) - putere(i,sv) <= 0 ) 
				ok=0;*/
		if ( ok ) ans++;
	}
	ans*=2;
	if ( ! (N%2) && ok ) ans--;
}

void scoate_prim() {
	long i;
	printf("{");
	for (i=0; i<nr; ++i)
		printf("%ld,",prim[i]);
	printf("%ld};", prim[nr]);
}

int main() {

	freopen(FIN, "r", stdin);
	scanf("%ld %ld", &N,&M);

	fclose(stdin);
	
	N--;ans=0;
	ciur((long) sqrt((double)M));
//	scoate_prim();
//	printf("%ld", nr);

	solve();

	freopen(FOUT, "w", stdout);
	printf("%ld\n", ans);
	fclose(stdout);
	return 0;
}