Cod sursa(job #1235836)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 30 septembrie 2014 19:19:03
Problema Pascal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<cstdio>
#include<iostream>
#define Nmax 5000010
using namespace std;

int dp[2], f[2], fact[2][Nmax];
int R, D, P, i, j, d, sol;

int main() {
    freopen("pascal.in", "r", stdin);
	freopen("pascal.out", "w", stdout);

	scanf("%d %d", &R, &D);

	for (d = 2 ; d <= D ; d++) {
		if (D % d == 0) {
			while (D % d == 0) { f[P]++; D /= d; }
			dp[P++] = d;
		}
	}
	
	for (i = 0 ; i < P ; i++) {
		d = dp[i];
		while (d <= R) {
			for (j = d ; j <= R ; j += d) 
				fact[i][j]++;
			d *= dp[i];
		}
	}

	for (i = 0 ; i < P ; i++) 
		for (j = 1 ; j <= R ; j++)
			fact[i][j] += fact[i][j-1];

	int M = R >> 1;
	bool last = false;
	for (j = 0 ; j <= M ; j++) {
		bool ok = true;
		for (i = 0 ; i < P ; i++) {
			int r = fact[i][R] - fact[i][j] - fact[i][R-j];
			if (r < f[i]) ok = false;
		}
		if (ok) { sol++; if (j == M) last = true; }
	}

	sol <<= 1;

    if (!(R&1) && last) sol--;
	printf("%d\n", sol);

	return 0;
}