Cod sursa(job #164514)

Utilizator anoukAnca Dumitrache anouk Data 24 martie 2008 12:53:38
Problema Pascal Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;
int P[10];

int howMany(int i, int d) {
	vector<int> div;
	if (d == 2)   div.push_back(2);
	if (d == 3)   div.push_back(3);
	if (d == 4) { div.push_back(2); div.push_back(2); }
	if (d == 5)   div.push_back(5);
	if (d == 6) { div.push_back(2); div.push_back(3); }
	int sol = 0;
	for (int k = 1; k < i; k++)
	{
		//cout << i - k + 1 << " " << k << "\n";
		if ((i - k + 1) % k == 0)
		{
			int x = (i - k + 1) / k;
			for (int j = 2; j < 7; j++)
			{
				int t = x;
				while (t % j == 0)
				{
					P[j - 2]++;
					t /= j;
				}
			}
		}
		else
		{
			int x = i - k + 1, y = k;
			/*while ( x % 2 == 0 && y % 2 == 0)
			{
				x /= 2;
				y /= 2;
			}
			while (x % 3 == 0 && y % 3 == 0)
			{
				x /= 3;
				y /= 3;
			}
			while (x % 5 == 0 && y % 5 == 0)
			{
				x /= 5;
				y /= 5;
			}*/
			for (int j = 2; j < 7; j++)
			{
				int t = y;
				while (t % j == 0)
				{
					P[j - 2]--;
					t /= j;
				}
			}
			for (int j = 2; j < 7; j++)
			{
				int t = x;
				while (t % j == 0)
				{
					P[j - 2]++;
					t /= j;
				}
			}
		}			
		int gasit = 1;
		for (int j = 0; j < div.size(); j++)
		{
			P[div[j] - 2]--;
			if (P[div[j] - 2] < 0) gasit = 0;
		}
		if (gasit) sol++;
		for (int j = 0; j < div.size(); j++)
			P[div[j] - 2]++;
	}
	return sol;
}

int main()
{
	FILE *fin = fopen("pascal.in", "r");
	FILE *fout = fopen("pascal.out", "w");

	int n, d;
	fscanf(fin, "%d%d", &n, &d);
	fprintf(fout, "%d\n", howMany(n, d));

	fclose(fin);
	fclose(fout);
	return 0;
}