整除问题

http://t.cn/Aip7eHBD

描述

给定n，a求最大的k，使n！可以被 a^k 整除但不能被 a^(k+1) 整除。

输入描述：

两个整数n(2<=n<=1000)，a(2<=a<=1000)

输出描述：

一个整数.

示例1

输入：

6 10

输出：

1

首先暴力求出来 n 的阶乘肯定不行，那么我们可以把 a 给拆分成若干个质因子之积，然后看下 2 ~ n 中包含多少个对应的质因子，就能得出来最多可以整除 a 的多少次方。比如 a 中有质因子p1, p2, p3，2~n中有对应的质因子num1, num2……. 个，那 k 的最大值也就是若干个 num 的最小值。

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>
using namespace std;

const int N = sqrt(1e3) + 10;
const int INF = INT_MAX;

vector<int> prime;
vector<bool> isPrime(N, true);

void Initial() {
	isPrime[0] = isPrime[1] = false;
	for (int i = 2; i < N; ++i) {
		if (!isPrime[i])
			continue;
		prime.push_back(i);
		for (int j = i * i; j < N; j += i)
			isPrime[j] = false;
	}
	return;
}

int main() {
	Initial();
	int n, a;
	while (cin >> n >> a)
	{
		map<int, int> exponentN;//存储n!的质因数分解
		for (int j = 2; j <= n; ++j) {
			int number = j;
			for (int i = 0; i < prime.size() && prime[i] <= number; ++i) {
				while (number % prime[i] == 0)
				{
					exponentN[prime[i]]++;
					number /= prime[i];
				}
			}
		}
		map<int, int> exponentA;//存储a的质因数分解
		for (int i = 0; i < prime.size(); ++i) {
			while (a % prime[i] == 0)
			{
				exponentA[prime[i]]++;
				a /= prime[i];
			}
		}
		int answer = INF;
		for (map<int, int>::iterator it = exponentA.begin(); it != exponentA.end(); ++it) {
			if (exponentN.find(it->first) == exponentN.end())
				answer = 0;
			else
				answer = min(answer, exponentN[it->first] / it->second);
		}
		printf("%d\n", answer);
	}
	return 0;
}