题解 | #整除问题#

将n!和a的质数分解求出来，那么n!和a相应质因子的指数之差就是答案。

#include <bits/stdc++.h>
#include <vector>
using namespace std;

const int Max = 1001;
vector<int> all(Max, 1);
vector<int> prime;

void initail(){
    
    all[0] = 0;
    all[1] = 0;

    for(int i = 2; i * i <= Max - 1; i++){
        if(all[i] == 1){
            for(int j = i; i * j <= Max - 1; j++){
                all[i * j] = 0;
            }
        }
    }

    for(int i = 2; i < Max; i++){
        if(all[i] == 1) prime.push_back(i);
    }

}


int main() {
    int n, a, i;
    cin >> n >> a;

    initail();

    vector<int> n_prime(n + 1, 0);
    i = 2;
    while(i <= n){  //得到n!的分解质因数的结果
        int temp = i;
        for(int j = 0; j < prime.size() && prime[j] <= temp; j++){
            while(temp % prime[j] == 0){
                temp /= prime[j];
                n_prime[prime[j]]++;
            }
        }
        i++;
    }

    vector<int> a_prime(n + 1, 0);
    for(int j = 0; j < prime.size() && prime[j] <= a; j++){
        while(a % prime[j] == 0){
            a /= prime[j];
            a_prime[prime[j]]++;
        }
    }

    int min = 1000;
    for(int j = 0; j <= n; j++){
        int cha = n_prime[j] - a_prime[j];
        if(all[j] == 1 && a_prime[j] != 0 && cha < min){
            min = cha;
        }
    }

    cout << min + 1;





}