题解 | #整除问题#

素数筛法求出小于特定值的所有素数后，将两数用质因数表示，通过数量关系求解最大整除

#include<cstdio>
#include<vector>
#include<map>
#define MAXN 1001
using namespace std;

vector<int> prime;
vector<bool> isprime(MAXN, true);

void initial() { //素数筛法整理MAXN包含的素数
    isprime[0] = false;
    isprime[1] = false;
    for (int i = 2; i < MAXN; i++) {
        if (!isprime[i]) { //false时不是素数
            continue;
        }
        prime.push_back(i);
        for (int j = i * i; j < MAXN; j += i) { //素数的倍数不是素数
            isprime[j] = false;
        }
    }
}

int main() {
    int n, a;
    initial();
    while (scanf("%d%d", &n, &a) != EOF) {
        map<int, int> afactor; //存放a的素因数
        for (int i = 0; i < prime.size(); i++) {//初始化map
            afactor.insert({prime[i], 0});
        }
        map<int, int> nfactor = afactor; //存放n阶乘的素因数
        for (int i = 0; i < prime.size() && prime[i] <= a; i++) {//更新a的map
            while (a % prime[i] == 0) {
                a /= prime[i];
                afactor[prime[i]]++;
            }
        }
        for (int i = 1; i <= n; i++) {//更新n的map
            int num = i;
            for (int j = 0; j < prime.size() && prime[j] <= num; j++) {
                while (num % prime[j] == 0) {
                    num /= prime[j];
                    nfactor[prime[j]]++;
                }
            }
        }
        int res = MAXN;
        for (int i = 0; i < afactor.size(); i++) {//对比两个map
            if (afactor[prime[i]]) {
                res = min(res, nfactor[prime[i]] / afactor[prime[i]]);
            }
        }
        printf("%d\n", res);
    }
    return 0;
}