10139 - Factovisors

Problem Link : https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1080

Solution Idea : m will divide n! if all the prime factors of m have equal or less power than the power of that prime number in n!. if m==1 than ans is true and m==0 ans is false.
so for this we have to prime factorize m first. then for every prime factor of m we need to check how many times it occurs in n! with proper function.

Solution :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

bool status[46400];
ll int a[46400];
ll int global=0;

vector<ll int>prime;

void sieve()
{
    ll int n=46380;
    ll int sq=sqrt(n);

    prime.push_back(2);

    for(ll int i=4; i<=n; i=i+2) status[i]=1;

    for(ll int i=3; i<=sq; i=i+2)
    {
        if(status[i]==0)
        {


            for(ll int j=i*i; j<=n; j=j+i)
            {
                status[j]=1;
            }
        }
    }
    status[1]=1;
    status[0]=1;

    for(ll int i=3; i<=n; i=i+2)
    {
        if(status[i]==0) prime.push_back(i);
    }
}

void nod(ll int n)
{
    ll int sq=sqrt(n);
    ll int res=1;

    for(ll int i=0; i<prime.size() && prime[i]<=sq; i++)
    {

        if(n%prime[i]==0)
        {
            while(n%prime[i]==0)
            {
                n=n/prime[i];
                a[prime[i]]++;
            }
            sq=sqrt(n);


        }
    }
    if(n!=1)
    {
        global=n;
    }

}
ll int  fact( ll int  n, ll int p )
{
    ll int  freq = 0;
    ll int x = n;

    while ( x )
    {
        freq += x / p;
        x = x / p;
    }

    return freq;
}

int main()
{
    ll int n,m,val,w,ca,cnt;
    sieve();

    while(scanf("%lld%lld",&n,&m)==2)
    {
        memset(a,0,sizeof(a));
        w=0;
        global=0;
        cnt=0;
        if(m==1 )
        {
            printf("%lld divides %lld!\n",m,n);
            continue;
        }
        nod(m);
        for(ll int i=0; i<prime.size() and prime[i]<=m; i++)
        {
            val=fact(n,prime[i]);

            ca=a[prime[i]];
            if(val>=ca)
            {
                if(val>0 and ca>0) cnt++;
            }
            else
            {
                w=1;
                break;
            }
        }
        if( w==0 and global!=0)
        {
            if(fact(n,global)>0)
            {
                printf("%lld divides %lld!\n",m,n);
                w=-5;
            }
            else w=3;
        }
        if((w==1 || cnt==0)and w!=-5)printf("%lld does not divide %lld!\n",m,n);
        else if(w==3) printf("%lld does not divide %lld!\n",m,n);
        else if(w==0) printf("%lld divides %lld!\n",m,n);

    }

}