给定n,a求最大的k,使n!可以被a^k整除但不能被a^(k+1)整除。
时间: 2024-03-07 21:46:34 浏览: 29
这是一个经典的问题,可以用数学方法解决。
首先,n! 中包含了多少个 a 呢?可以用 n//a + n//a^2 + n//a^3 + ... 的方法求出,其中 "//" 表示整除。例如,n=1000,a=5,那么 n! 中包含的 5 的个数就是 1000//5 + 1000//25 + 1000//125 + 1000//625 = 200 + 40 + 8 + 1 = 249。
现在我们需要找到 k,使得 n! 中包含了 k 个 a,但不包含 k+1 个 a。我们可以用二分法来查找 k。具体地,我们先猜一个 k0,然后计算 n! 中包含的 a 的个数,记为 cnt。如果 cnt >= k0+1,那么说明 k >= k0+1,否则说明 k <= k0。于是我们可以将搜索范围缩小到 [l, r],其中 l=k0, r=2k0。每次计算 cnt 都需要 O(log n) 的时间,一共需要进行 O(log k) 次计算,因此总时间复杂度为 O(log^2 n)。
下面是 Python 代码实现:
```python
def count_factors(n, a):
cnt = 0
while n >= a:
cnt += n // a
n //= a
return cnt
def max_k(n, a):
l, r = 0, n
while l < r:
k = (l + r + 1) // 2
cnt = count_factors(n, a**k)
if cnt >= k+1:
l = k
else:
r = k-1
return l
```
可以这样调用:
```python
n = 1000
a = 5
print(max_k(n, a)) # 输出 249
```