Cod sursa(job #1065031)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 22 decembrie 2013 17:41:08
Problema Pascal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include<cstdio>
#include<vector>

using namespace std ;

class Facts{
public:
	int r2, r3, r5 ; 
};

int nr, D2, D3, D5, D, R ;
vector <Facts> V ;

void FactD() ;
void FactR() ;
void Solve() ;
void Write() ;

int main() {
	freopen("pascal.in", "r", stdin) ;
	freopen("pascal.out", "w", stdout) ;
	scanf("%d %d", &R, &D) ;
	FactD() ;
	FactR() ;
	Solve() ;
	Write() ;
	return 0 ;
}

void FactD() {
	while(D % 2 == 0) {
		D /= 2 ;
		++D2 ;
	}
	while(D % 3 == 0) {
		D /= 3 ; 
		++D3 ;
	}
	while(D % 5 == 0) {
		D /= 5 ;
		++D5 ;
	}
}

void FactR() {
	int i, x, y ;
	V.resize(R + 1) ;
	for (i = 1; i <= R; ++i) {
		x = i ;
		V[i] = V[i - 1] ;
		if (x % 30 == 0) {
			y = 30 ;
			V[x].r2 += 1 + V[x / y].r2 - V[x / y - 1].r2 ;
			V[x].r3 += 1 + V[x / y].r3 - V[x / y - 1].r3 ;
			V[x].r5 += 1 + V[x / y].r5 - V[x / y - 1].r5 ; 
			continue ;
		}
		if (x % 10 == 0) {
			y = 10 ;
			V[x].r2 += 1 + V[x / y].r2 - V[x / y - 1].r2 ;
			V[x].r3 += V[x / y].r3 - V[x / y - 1].r3 ;
			V[x].r5 += 1 + V[x / y].r5 - V[x / y - 1].r5 ; 
			continue ;
		}
		if (x % 15 == 0) {
			y = 15 ;
			V[x].r2 += V[x / y].r2 - V[x / y - 1].r2 ;
			V[x].r3 += 1 + V[x / y].r3 - V[x / y - 1].r3 ;
			V[x].r5 += 1 + V[x / y].r5 - V[x / y - 1].r5 ; 
			continue ;
		}
		if (x % 6 == 0) {
			y = 6 ;
			V[x].r2 += 1 + V[x / y].r2 - V[x / y - 1].r2 ;
			V[x].r3 += 1 + V[x / y].r3 - V[x / y - 1].r3 ;
			V[x].r5 += V[x / y].r5 - V[x / y - 1].r5 ; 
			continue ;
		}
		if (x % 2 == 0) {
			y = 2 ;
			V[x].r2 += 1 + V[x / y].r2 - V[x / y - 1].r2 ;
			V[x].r3 += V[x / y].r3 - V[x / y - 1].r3 ;
			V[x].r5 += V[x / y].r5 - V[x / y - 1].r5 ; 
			continue ;
		}
		if (x % 3 == 0) {
			y = 3 ;
			V[x].r2 += V[x / y].r2 - V[x / y - 1].r2 ;
			V[x].r3 += 1 + V[x / y].r3 - V[x / y - 1].r3 ;
			V[x].r5 += V[x / y].r5 - V[x / y - 1].r5 ; 
			continue ;
		}
		if (x % 5 == 0) {
			y = 5 ;
			V[x].r2 += V[x / y].r2 - V[x / y - 1].r2 ;
			V[x].r3 += V[x / y].r3 - V[x / y - 1].r3 ;
			V[x].r5 += 1 + V[x / y].r5 - V[x / y - 1].r5 ; 
			continue ;
		}
		/*
		V[i] = V[i - 1];
		while(x % 2 == 0) {
			x /= 2 ;
			++V[i].r2 ;
		}
		while(x % 3 == 0) {
			x /= 3 ; 
			++V[i].r3 ;
		}
		while(x % 5 == 0) {
			x /= 5 ;
			++V[i].r5 ;
		}*/
		
	}
}

void Solve() {
	int i, d2, d3, d5, mij = R >> 1 ;
	for (i = 1; i <= mij; ++i) {
		d2 = V[R].r2 - (V[i].r2 + V[R - i].r2) ;
		d3 = V[R].r3 - (V[i].r3 + V[R - i].r3) ;
		d5 = V[R].r5 - (V[i].r5 + V[R - i].r5) ;
		if (d2 >= D2 && d3 >= D3 && d5 >= D5) {
			++nr ;
		}
	}
	nr *= 2 ;
	if (R % 2 == 0) --nr ;
}

void Write() {
	printf("%d", nr) ;
}