这个问题要求我们计算在一个给定进制下，\(N!\)（\(N\)的阶乘）的末尾有多少个零。为了理解和解决这个问题，首先我们需要搞清楚什么是阶乘末尾零以及如何与给定进制相关联。

问题分析

1. 阶乘末尾零的定义：
   阶乘末尾的零是指数字中末尾有多少个连续的零。比如，\(10! = 3,628,800\)，其末尾有两个零。我们可以通过分解阶乘的因数来确定末尾零的数量。通常在十进制下（进制 \(a = 10\)），末尾零的数量等于阶乘中包含多少个因子 \(10\)，而 \(10 = 2 \times 5\)，所以末尾零的数量取决于阶乘中因子 \(2\) 和 \(5\) 的数量，较小的那个数决定了末尾零的个数。

2. 给定进制：
   当问题要求计算在进制 \(a\) 下的末尾零时，我们的思路是：

   • 找出进制 \(a\) 的质因数分解。
   • 对每个质因数 \(p\)，计算在 \(N!\) 中能得到多少个因子 \(p\)，这就是 \(p\) 在 \(N!\) 中出现的次数。
   • 对于 \(a = p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k}\)，末尾零的数量是所有质因数 \(p_1, p_2, \dots, p_k\) 的个数限制因子数的最小值。

3. 计算方法：

   • 对于一个质因数 \(p\)，在 \(N!\) 中出现的次数可以通过以下方式计算： \[ \text{count}(p) = \left\lfloor \frac{N}{p} \right\rfloor + \left\lfloor \frac{N}{p^2} \right\rfloor + \left\lfloor \frac{N}{p^3} \right\rfloor + \dots \] 直到 \(p^k > N\) 为止。这个公式就是累加每个倍数中包含的因子个数。

解决步骤

1. 分解进制：首先对进制 \(a\) 进行质因数分解，得到 \(a = p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k}\)。
2. 计算每个质因数在 \(N!\) 中的次数：对每个质因数 \(p_i\)，使用上述的公式来计算在 \(N!\) 中包含多少个 \(p_i\)。
3. 根据质因数的指数调整：对于每个质因数 \(p_i\)，需要将其出现次数除以它在进制分解中对应的指数 \(e_i\)，然后选择所有质因数的结果中的最小值作为 \(N!\) 在进制 \(a\) 下末尾零的个数。

代码实现

def prime_factors(a):
    factors = []
    # 对a进行质因数分解
    d = 2
    while d * d <= a:
        count = 0
        while a % d == 0:
            a //= d
            count += 1
        if count > 0:
            factors.append((d, count))
        d += 1
    if a > 1:
        factors.append((a, 1))
    return factors

def count_p_in_factorial(N, p):
    # 计算p在N!中出现的次数
    count = 0
    power = p
    while power <= N:
        count += N // power
        if power > N // p:
            break
        power *= p
    return count

def trailing_zeroes_in_factorial(N, a):
    # 获取a的质因数分解
    factors = prime_factors(a)
    
    min_zeroes = float('inf')
    
    # 对每个质因数p_i，计算N!中p_i的个数
    for p, e in factors:
        count = count_p_in_factorial(N, p)
        # 计算p的贡献，应该是count // e
        min_zeroes = min(min_zeroes, count // e)
    
    return min_zeroes

# 输入
N, a = map(int, input().split())

# 输出
print(trailing_zeroes_in_factorial(N, a))

解释

1. prime_factors(a)：该函数对整数 \(a\) 进行质因数分解，返回一个列表，其中每个元素是一个二元组 \((p, e)\)，表示 \(a = p^e \times \dots\) 。
2. count_p_in_factorial(N, p)：这个函数用来计算一个质因数 \(p\) 在 \(N!\) 中出现的次数。
3. trailing_zeroes_in_factorial(N, a)：主函数，用来计算在进制 \(a\) 下，\(N!\) 末尾零的数量。它通过质因数分解进制 \(a\)，然后计算每个质因数在 \(N!\) 中的贡献，最终得到最小的零的数量。

时间复杂度分析

• 质因数分解时间复杂度是 \(O(\sqrt{a})\)，因为我们对 \(a\) 进行质因数分解。
• 对于每个质因数 \(p\)，计算其在 \(N!\) 中出现的次数需要 \(O(\log_p N)\) 时间，因此总的复杂度为 \(O(\sqrt{a} \times \log N)\)。

考虑到 \(N\) 可能非常大（最大可以到 \(10^{18}\)），但通常情况下进制 \(a\)的质因数数量远小于 \(N\)，因此这个方法是有效的。

示例

输入

200 10

输出

59

这段代码可以准确地计算出在进制 \(a\) 下，\(N!\) 的末尾零的数量。

对 \(a\) 进行因子分解，然后分别找 \(1-N\) 中有多少个因子既可。令 \(k\) 是最大的因子，则答案为 \(\sum_{i=1}^{\infin}\lfloor \frac{N}{k^i}\rfloor\)。

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
int N,a,apm[25],apn[25],cnt;//apm:a的素因数 apn:a的素因数在素因数分解中的数量

signed main(){
    
    cin>>N>>a;int b=a;
    for(int i=2;i*i<=b;i++){
        if(b%i==0){
            cnt++;
            while(b%i==0){
                b/=i;
                apn[cnt]++;
            }apm[cnt]=i;
        }
    }
    if(b!=1){
        cnt++;
        apn[cnt]++;
        apm[cnt]=b;
    }
//分解素因数
    int ans=-1;
    for(int i=1;i<=cnt;i++){//枚举每个素因数
        int ans1=0;
        int pd=apm[i];
        ans1+=(N/pd);
        do{//这里如果用pd*apm[i]可能爆long long
            pd*=apm[i];
            ans1+=(N/pd);
        }while(pd<=(N+apm[i])/apm[i]);
        ans1/=apn[i];
        ans=min(ans,ans1);
    }
    cout<<ans<<endl;
}