描述
给定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;
}