题解 | #整除问题#

主打一个分解质因数

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <cmath>
using namespace std;

int main()
{
    int a, n, i, j;
    cin >> n >> a;
    // 1.先对n！分解质因数
    int yinzi[n], zancun;
    for (i = 0; i < n; i++)
    {
        yinzi[i] = 0;
    }
    for (i = 1; i <= n; i++) // 从1~n都是n!的因子，但是我们还要对其进行拆解，把因子改成质因子
    {
        zancun = i;
        for (j = 2; j < zancun; j++)
        {
            while (zancun % j == 0)
            {
                zancun /= j;
                yinzi[j]++;
                // cout << "因子：" << j << ",从i为：" << i << "来的" << endl;
            }
        }
        yinzi[zancun]++;
        // cout << "因子：" << zancun << ",从i为：" << i << "来的" << endl;
    }
    // for (i = 0; i < n; i++)
    // {
    //     cout << yinzi[i] << endl;
    // }
    // 2.对a分解质因数
    int temp[a];
    zancun = a;
    for (i = 0; i < zancun; i++)
    {
        temp[i] = 0;
    }
    for (i = 2; i <= zancun; i++)
    {
        while (zancun % i == 0)
        {
            zancun /= i;
            temp[i]++;
            // cout << "因子：" << i << endl;
        }
    }
    int minx = 10000;
    for (i = 2; i < a; i++)
    {
        // cout << "hdu" << endl;
        if (temp[i] != 0 && yinzi[i] != 0)
        {
            // cout << yinzi[i] << temp[i] << endl;
            minx = min(minx, yinzi[i] / temp[i]);
        }
    }
    cout << minx;

    return 0;
}