uva 10139 求n的阶乘能否整除m

末蓝、 2022-08-04 00:00 196阅读 0赞

n跟m的范围都是0-2^31，只能用质因数分解把m分成若干个质数相乘的形式，然后对每个质因数的数量判断n的阶乘中这个质因数的数量是不是足够，不够的话就不行。

最后m可能是一个质数，没有被2到根号m中的质数分解，于是分解过后要是m还要大于n，这也不能分解，但是当n==0，m==1时是可以的，这种情况要特判。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;
        char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=500000;
    bitset <N>vis;
    int prime[200000];
    
    int getNum(int i,int m)
    {
        int res=0;
        while(m)
        {
            res+=m/prime[i];
            m/=prime[i];
        }
        return res;
    }
    
    int main()
    {
        int p=-1;
        for(int i=2;i<N;i++)
        {
            if(!vis[i]) prime[++p]=i;
            for(int j=0;j<=p && prime[j]*i<N;j++)
            {
                vis[prime[j]*i]=1;
                if(i%prime[j]==0)break;
            }
        }
    
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            if(n>=m)
            {
                printf("%d divides %d!\n",m,n);
                continue;
            }
            bool can=1;
            int record=m;
            for(int i=0;i<=p && can && prime[i]*prime[i]<=m;i++)
            {
                int tmp=0;
                while(m%prime[i]==0)//质因数分解
                {
                    tmp++;            //当前质因数的个数
                    m/=prime[i];
                }
                if(tmp){
                    int tmp2=getNum(i,n); //n！中prime[i]的个数
                    if(tmp2<tmp) can=0;
    
                }
            }
            if(n!=0 && m>n)can=0;///
            if(can) printf("%d divides %d!\n",record,n);
            else printf("%d does not divide %d!\n",record,n);
    
        }
        return 0;
    }