题意分析

本题主要围绕阶乘和整除的概念展开。给定两个非负整数 n 和 m，需要判断 m 是否能整除 n!。其中阶乘函数 n! 的定义为：当 n = 0 时，n! = 1；当 n > 0 时，n! = n * (n - 1)!。而若存在整数 k 使得 k * a = b，则称 a 能整除 b。程序的输入是若干行，每行包含两个小于 2^31 的非负整数 n 和 m，输出则是对于每一行输入，表明 m 是否能整除 n! 的信息。

解题思路

本题的核心思路是对 m 进行质因数分解，然后计算 n! 中每个质因数的个数，通过比较 m 中每个质因数的个数和 n! 中对应质因数的个数来判断 m 是否能整除 n!。具体步骤如下：

1. 素数筛选：使用埃拉托斯特尼筛法的优化版本（线性筛）找出一定范围内（本题中为 N = 1000000）的所有素数，并存储在数组 p 中。
2. 质因数分解：对于输入的 m，将其分解为质因数及其对应的个数，存储在 vector<factor> 类型的 v 中。
3. 计算 n! 中质因数的个数：对于 v 中的每个质因数，计算 n! 中该质因数的个数。可以利用公式：n! 中质因数 p 的个数为 n/p + n/p^2 + n/p^3 + ...。
4. 判断整除关系：比较 m 中每个质因数的个数和 n! 中对应质因数的个数，如果 m 中某个质因数的个数大于 n! 中该质因数的个数，则 m 不能整除 n!；否则，m 能整除 n!。

代码解释

//poj2649
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N=1000000;
bool prime[N+1];
long long p[N+1];
int k=0;

// 线性筛法求素数
void getprime()
{
    memset(prime,0,sizeof(prime));
    prime[0]=1;
    prime[1]=1;
    for(int i=2;i<=N;i++)
    {
        if(!prime[i]) p[k++]=i;
        for(int j=0;j<k;j++)
        {
            if(p[j]*i>N) break;
            prime[p[j]*i]=1;
            if(i%p[j]==0) break;
        }
    }
}

// 定义结构体存储质因数及其个数
struct factor//a：素因子，k素因子的个数
{
    int a,k;
};
vector<factor> v;

// 对t分解质因子，结果存在v中
void getfen(int t)
{
    v.clear();
    for(int i=0;p[i]*p[i]<=t;i++)
    {
        if(t%p[i]==0)
        {
            factor a;
            a.a=p[i];
            a.k=0;
            while(t%p[i]==0)
            {
                a.k++;
                t=t/p[i];
            }
            v.push_back(a);
        }
    }
    if(t&&t!=1)
    {
        factor a;
        a.a=t;
        a.k=1;
        v.push_back(a);
    }
}

int main()
{
    getprime();
    int n,m;
    while(cin>>m>>n)
    {
        getfen(n);
        int flag=1;
        for(int i=0;i<v.size();i++)
        {
            int kk=0,l=v[i].a;//kk代表m中素因子v[i].a的个数
            while(m/l)
            {
                kk+=m/l;
                l=l*v[i].a;
            }
            if(kk<v[i].k)
            {
                flag=0;
                break;
            }
        }
        if(m==0||n==0) flag=0;
        if(flag)
            cout<<n<<" divides "<<m<<"!"<<endl;
        else cout<<n<<" does not divide "<<m<<"!"<<endl;
    }
}

1. 素数筛选函数 getprime：使用线性筛法找出 2 到 N 之间的所有素数，存储在数组 p 中。prime 数组用于标记某个数是否为素数，k 记录素数的个数。
2. 质因数分解函数 getfen：对于输入的 t，将其分解为质因数及其对应的个数，存储在 vector<factor> 类型的 v 中。通过遍历素数数组 p，找出 t 的所有质因数，并计算其个数。
3. 主函数 main：
   • 调用 getprime 函数生成素数表。
   • 循环读取输入的 n 和 m。
   • 调用 getfen 函数对 m 进行质因数分解。
   • 计算 n! 中每个质因数的个数，并与 m 中对应质因数的个数进行比较。
   • 根据比较结果输出 m 是否能整除 n! 的信息。

复杂度分析

• 时间复杂度：素数筛选的时间复杂度为 $O(N)$，质因数分解的时间复杂度为 $O(\sqrt{m})$，计算 n! 中质因数个数的时间复杂度为 $O(\log n)$，因此总的时间复杂度为 $O(N + T(\sqrt{m} + \log n))$，其中 T 为输入的行数。
• 空间复杂度：主要用于存储素数表和质因数分解结果，空间复杂度为 $O(N)$。

注意事项

1. 边界条件：当 n = 0 或 m = 0 时，需要特殊处理，直接判定 m 不能整除 n!。
2. 素数筛选范围：由于输入的 n 和 m 小于 2^31，因此素数筛选的范围 N 可以设置为一个合适的值，本题中设置为 1000000。
3. 质因数分解：在对 m 进行质因数分解时，需要注意处理 m 本身为素数的情况。