题解 | #整除问题#

#include <algorithm>
#include <climits>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
// 质因数分解
void decompose_prime(vector<int>& factor, int a)
{
    int i = 2;
    while(a != 1)
        {
            if(a % i == 0)
            {
                ++factor[i];
                a /= i;
            }
            else ++i;
        }
}

int main() {
    int n, a, ret, i, j, tmp;
    while (cin >> n >> a) 
    { 
        int size = 1000;
        // 保存每一项质因数的指数
        vector<int> factor_n(size, 0), factor_a(size, 0);
        // 分解a
        decompose_prime(factor_a, a);

        // 分解n！
        for(i = 2; i <= n; ++i)
        {
            // 分解阶乘的每一项
            decompose_prime(factor_n, i);
        }
        // 选最大的幂次
        i = INT_MAX;
        for(j = 2; j < size; ++j)
        {
            if(factor_a[j] == 0) continue;
            else
            {
                // k = factor_n[j]/factor_a[j]
                i = min(i, factor_n[j]/factor_a[j]);
            }
        }
        cout << i << endl;
    }
}