整除问题

思路

首先暴力求出来 n 的阶乘肯定不行，那么我们可以把 a 给拆分成若干个质因子之积，然后看下 2 ~ n 中包含多少个对应的质因子，就能得出来最多可以整除 a 的多少次方。

比如 a 中有质因子 、、，2 ~ n 中有对应的质因子 、... 个，那 k 的最大值也就是若干个 num 的最小值。

大致思路其实很简单，但是细节是需要注意的，比如 a = 2 * 2，有两个 2，我们不仅要统计质因数，还要统计质因数的个数。

#include<iostream>
#include<vector>

using namespace std;
//统计 num 中的质因子数
void getPrime(vector<int>& factors, int num){
    for(int i = 2; i*i <= num; i ++){
        while(num % i == 0){
            factors[i] ++;
            num /= i;
            if(num <= 1) return;
        }
    }
    if(num > 1) factors[num] ++;
}

int main(){
    int n, a;
    while(cin >> n >> a){
        vector<int> factor_a(1000), factor_n(1000);
        getPrime(factor_a, a);
        for(int i = 2; i <= n; i ++)
            getPrime(factor_n, i);
        int k = 1000;
        for(int i = 2; i <= a; i ++){
            if(factor_a[i]) k = min(k, factor_n[i]/factor_a[i]);
        }
        cout << k << endl;
    }
    return 0;
}