1141 - Number Transformation

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1141

Solution :

#include<bits/stdc++.h>

using namespace std;

bool status[1021];

vector<int>factor;
vector< int>prime;

void sieve()
{
    int n=1020;
    int sq=sqrt(n);

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

    prime.push_back(2);

    for( int i=3; i<=sq; i=i+2)
    {
        if(status[i]==false)
        {
            for(int j=i*i; j<=n; j=j+i) status[j]=true;
        }
    }
    status[1]=1;
    status[0]=1;

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

int visited[1020];

int bfs(int s,int d)
{
    int u,p;
    memset(visited,-1,sizeof(visited));

    queue<int>q;

    q.push(s);
    visited[s]=0;

    while(!q.empty())
    {
        u=q.front();
        q.pop();

        for(int i=0; prime[i]<u; i++)
        {
            if(u%prime[i]==0)
            {
                factor.push_back(prime[i]);
            }
        }


        for(int i=0; i<factor.size(); i++)
        {
            p=u+factor[i];

            if(visited[p]==-1 and p<=d)
            {
                visited[p]=visited[u]+1;
                q.push(p);

            }
        }
        factor.clear();
    }
    return visited[d];


}

int main()
{
    int t,a,b,ans;
    sieve();
    scanf("%d",&t);

    for(int ca=1; ca<=t; ca++)
    {
        scanf("%d%d",&a,&b);
        ans=bfs(a,b);
        printf("Case %d: %d\n",ca,ans);
        factor.clear();
    }
}

1289 - LCM from 1 to n

Problem link : http://lightoj.com/volume_showproblem.php?problem=1289

Tutorial : https://nlognblog.wordpress.com/2015/12/01/light-oj1289-lcm-from-1-to-n/

Hint : 

1. When a problem says that you have to do modulo 2^32 (and it requires only addition, subtraction and multiplication) then just take them as unsigned integers and do regular operations. Just think that the compiler uses 32 bit operations, and if it overflows, then the most significant bits will be lost but the least significant 32 bits will be correct, which is equivalent to modulo 2^32.

Solution :

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

using namespace std;

const int MAX = 100000000;  // 10^8
const int LMT =     10000;  // sqrt(MAX)

int _c[(MAX>>6)+1];

int  primes[5761482];

#define IsComp(n)  (_c[n>>6]&(1<<((n>>1)&31)))

#define SetComp(n) _c[n>>6]|=(1<<((n>>1)&31))
ll mnt=0;
void sieve()
{
    int x=0;

    for (int i = 3; i <= LMT; i += 2)
        if (!IsComp(i))
            for (int j = i*i; j <= MAX; j += i+i)
                SetComp(j);

    primes[x++]=2;
    mnt++;
    for (int i=3; i <= MAX; i += 2)
        if (!IsComp(i))
        {
            primes[x++]=i;
            mnt++;
        }
}

ll store[5761482];

void precal()
{
    store[0]=2;

    for(ll i=1; i<mnt; i++)
    {
        store[i]=store[i-1]*primes[i];
    }
}
ll cal(ll n)
{
    ll temp,ret=1;

    for(ll i=0; primes[i]*primes[i]<=n; i++)
    {
        temp=n;
        temp=temp/primes[i];
        while(temp>=primes[i])
        {
            temp=temp/primes[i];
            ret=ret*primes[i];
        }
    }
    return ret;

}

int main()
{
    ll  n,val,sq,q,rs,cnt,ans,t,ca=1;
    sieve();
    precal();
    scanf("%u",&t);

    while(t--)
    {
        scanf("%u",&n);

        ans=cal(n);

        val=upper_bound(primes,primes+mnt,n)-primes;
        val--;
        ans=ans*store[val];

        printf("Case %u: %u\n",ca,ans);
        ca++;
    }
}

10680 - LCM

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

Solution Idea : http://pavelsimo.blogspot.com/2012/06/uva-10680-lcm.html

Solution :

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

using namespace std;

bool status[1000002];

vector<ll int>prime;

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

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

    prime.push_back(2);

    for(ll int i=3; i<=sq; i=i+2)
    {
        if(status[i]==false)
        {
            for(int j=i*i; j<=n; j=j+i) status[j]=true;
        }
    }
    status[1]=1;
    status[0]=1;

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

ll int fact[1000005];

int main()
{
    ll int n,val,sq,q,rs,cnt,ans;
    sieve();
    while(scanf("%lld",&n) and n)
    {
        memset(fact,0,sizeof(fact));

        fact[1]=1;
        ans=1;
        for(ll int j=0; j<prime.size() and prime[j]<=n; j++)
        {
            val=prime[j];

            while(val<=n)
            {
                val=val*prime[j];

            }
            val=val/prime[j];
            fact[prime[j]]=val;

        }

        ll int cc=fact[5];
        cnt=0;
        while(fact[5]>1)
        {
            fact[5]=fact[5]/5;
            cnt++;
        }
        for(ll int k=cnt; k>0; k--)
        {
            fact[2]=fact[2]/2;
        }
        for(int i=1; i<=1000000; i++)
        {
            if(fact[i]!=0) ans=((ans%10)*(fact[i]%10))%10;
        }
        printf("%lld\n",ans);
    }

}

11388 - GCD LCM

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

Solution Idea : http://blog.forthright48.com/2015/08/uva-11388-gcd-lcm.html

Solution :

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main()

{

    ll int ca,g,l,a,b;

    scanf("%lld",&ca);

    while(ca--)

    {

        scanf("%lld%lld",&g,&l);

        if(l%g!=0)

        {

            printf("-1\n");

        }

        else

        {

            a=g;

            b=l;

            printf("%lld %lld\n",a,b);

        }

    }

}

1138 - Trailing Zeroes (III)

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1138

Solution idea : binary search problem..take any number and find how many trailing zeros are in it...compare it with required number and continue the process.

Solution :

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll int fact ( ll int n,ll int p  )
{

    ll int x = n;
    ll int freq = 0;

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


    return freq;
}

ll int func(ll int n)
{
    ll int hi=1000000000000000000,lo=0,mid,ans,a1,a2,w=-1;

    while(lo<=hi)
    {
        mid=(lo+hi)/2;

        a1=fact(mid,2);
        a2=fact(mid,5);
        a1=min(a1,a2);

        if(a1==n)
        {
            hi=mid-1;
            ans=mid;
            w=0;
        }
        else if(a1>n)
        {
            hi=mid-1;
        }
        else lo=mid+1;
    }
    if(w==0) return ans;
    else return -1;
}

int main()
{
    ll int t,n,ans;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld",&n);
        ans=func(n);

        if(ans==-1) printf("Case %lld: impossible\n",ca);
        else printf("Case %lld: %lld\n",ca,ans);

    }
}

1138 - Trailing Zeroes (III)

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1138

Solution idea : binary search problem..take any number and find how many trailing zeros are in it...compare it with required number and continue the process.

Solution :

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll int fact ( ll int n,ll int p  )
{

    ll int x = n;
    ll int freq = 0;

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


    return freq;
}

ll int func(ll int n)
{
    ll int hi=1000000000000000000,lo=0,mid,ans,a1,a2,w=-1;

    while(lo<=hi)
    {
        mid=(lo+hi)/2;

        a1=fact(mid,2);
        a2=fact(mid,5);
        a1=min(a1,a2);

        if(a1==n)
        {
            hi=mid-1;
            ans=mid;
            w=0;
        }
        else if(a1>n)
        {
            hi=mid-1;
        }
        else lo=mid+1;
    }
    if(w==0) return ans;
    else return -1;
}

int main()
{
    ll int t,n,ans;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld",&n);
        ans=func(n);

        if(ans==-1) printf("Case %lld: impossible\n",ca);
        else printf("Case %lld: %lld\n",ca,ans);

    }
}

1090 - Trailing Zeroes (II)

Problem Link :

Solution Idea : Interesting one. we have to find the number of 2's and number of 5's in (nCr*p^q). the ans is min(total number of 2's,total number of 5's).

Solution :

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

using namespace std;

ll int fact ( ll int n,ll int p  )
{

    ll int x = n;
    ll int freq = 0;

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


    return freq;
}

ll int fcnt(ll int n,ll int m)
{
    ll int cnt=0;

    while(n>0 and !(n%m))
    {
        n=n/m;
        cnt++;
    }
    return cnt;
}

int main()
{
    ll int t,n,r,p,q,a1,a2,a3,b1,b2,cnt,b3;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld%lld%lld%lld",&n,&r,&p,&q);
        cnt=0;
        a1=fact(n,2);
        b1=fact(n,5);
        a2=fact(r,2);
        b2=fact(r,5);
        a3=fact(n-r,2);
        b3=fact(n-r,5);
        a1=a1-(a2+a3);
        b1=b1-(b2+b3);


        a2=fcnt(p,2)*q;
        b2=fcnt(p,5)*q;

        a3=a1+a2;
        b3=b1+b2;

        a1=min(a3,b3);

        printf("Case %lld: %lld\n",ca,a1);

    }

}

1028 - Trailing Zeroes (I)

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1028

Solution Idea : number of divisors

Solution :

#include<bits/stdc++.h>
#define ll long long
using namespace std;

bool status[1000009];

vector<ll int>prime;

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

    prime.push_back(2);

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

    for(int i=3;i<=sq;i=i+2)
    {
        if(status[i]==0)
        {
                   for(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);
    }
}

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

    for(int i=0;i<prime.size() && prime[i]<=sq;i++)
    {
        int cnt=1;
  int c=prime[i];
        while(n%prime[i]==0)
        {
            n=n/prime[i];
            cnt++;
        }
        sq=sqrt(n);

        res= res*(cnt);
    }
    if(n!=1)
    {
        res=res*2;
    }
    return res;
}

int main()
{
    sieve();
   ll int t,n,ans;
   scanf("%lld",&t);

   for(ll int ca=1;ca<=t;ca++)
   {
       scanf("%lld",&n);
       ans=nod(n);
       ans--;
       printf("Case %lld: %lld\n",ca,ans);
   }

}

1067 - Combinations

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1067

Solution Idea : ans is nCr. which is n!/r!(n-r)! .  as n and k is below <=10^6. so first we store the value of factorial 1 to 10^6 mod 1000003 in fact array.

then for finding n!/r!(n-r)! we need to find the modular inverse of r!(n-r)!. then ans is( n! * modular inverse of r!(n-r)!) mod 1000003.

Solution :

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll int X=-1,Y=-1;

ll int ext_gcd ( ll int A,ll int B)
{
    ll int x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1;
    y2 = 0;
    x1 = 0;
    y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y )
    {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    X = x2;
    Y = y2;

    return r2;
}

ll int minv(ll int a,ll int m)
{
    ext_gcd(a,m);

    X=X%m;

    if(X<0) X=X+m;

    return X;
}


ll int fact[1000001];
ll int m=1000003;

int main()
{
    fact[0]=1;

    for(ll int i=1; i<=1000000; i++)
    {
        fact[i]=((fact[i-1]%m)*(i%m))%m;
    }

    ll int t,n,r,ans;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld%lld",&n,&r);

        ans= ((fact[r]%m)*(fact[n-r]%m))%m;
        ans=minv(ans,m);
        ans=(fact[n]*ans)%m;
        printf("Case %lld: %lld\n",ca,ans);
    }

}

1214 - Large Division

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1214

Solution Idea : manual division.

Solution :

#include<bits/stdc++.h>
#define ll long long
using namespace std;

char s[10002];

int main()
{

    ll int b,t,sz,res,val,p,cnt,i,w;

    scanf("%lld",&t);
    getchar();
    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%s%lld",s,&b);
        getchar();

        if(b<0) b=-1*b;

        p=b,cnt=0,res=-1,val=0,i=0,w=-1;

        sz=strlen(s);
        if(s[0]=='-')i++;
        val=s[i]-48;
        while(i<sz)
        {
            if(val>=b)
            {
                val=val%b;
                i++;
                w=0;
            }

            else
            {
                i++;
                if(w==0)
                {
                    i--;
                    w=-1;
                }
                if(i<sz )
                {
                    val=(val*10)+s[i]-48;

                }
            }

        }
        if(val==0)
        {
            printf("Case %lld: divisible\n",ca);
        }
        else printf("Case %lld: not divisible\n",ca);
    }


}

10176 - Ocean Deep! - Make it shallow!!

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

Solution idea : take every digit and represent it in decimal and mod it.. update the result every time...if the final result is divisible by m than ans is YES.

Solution : 

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll int bigmod(ll int b,ll int p,ll int m)
{
    if(p==0) return 1%m;

    else if(p%2==0)
    {
        ll int y= bigmod(b,p/2,m);

        return (y*y)%m;
    }
    else return (b*(bigmod(b,p-1,m)))%m;
}

ll int s[10002];

int main()
{
    char ch;
    ll int index,m=131071,res,val;

    while(scanf("%ch",&ch)==1)
    {
        index=0;
        s[index]=ch-48;
        index++;
        res=0;
        val=0;
        while(scanf("%ch",&ch)==1)
        {
            if(ch=='#') break;
            if(ch=='1'||ch=='0')
            {
                s[index]=ch-48;
                index++;
            }

        }
        getchar();
        for(ll int i=0; i<index; i++)
        {
            val=(s[i]*bigmod(2,index-1-i,m))%m;
            res=res+val;
        }
        if(res%m==0) printf("YES\n");
        else printf("NO\n");
    }

}

Bigmod recursive method source code

Tutorial Link : http://blog.forthright48.com/2015/08/modular-exponentiation.htm

Code :

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

using namespace std;

ll int bigmod(ll int b,ll int p,ll int m)
{
    if(p==0) return 1%m;

    else if(p%2==0)
    {
        ll int y= bigmod(b,p/2,m);

        return (y*y)%m;
    }
    else return (b*(bigmod(b,p-1,m)))%m;
}

int main()
{
 ll int b,p,m;

 scanf("%lld%lld%lld",&b,&p,&m);

 printf("%lld",bigmod(b,p,m));


}

1024 - Eid

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1024

Solution Idea : it's visible that ans is the lcm of all numbers given. but the ans can be very big. so we need to calculate the lcm in efficient way and store the result into an array.

Solution :

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

using namespace std;

bool status[10002];

vector<ll int>prime;

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

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

    prime.push_back(2);

    for(ll int i=3; i<=sq; i=i+2)
    {
        if(status[i]==false)
        {
            for(int j=i*i; j<=n; j=j+i) status[j]=true;
        }
    }
    status[1]=1;
    status[0]=1;

    for(ll int i=3; i<=n; i=i+2)
    {
        if(status[i]==0) prime.push_back(i);
    }
}
ll int res[1000000];
ll int fact[10001];
ll int multiply(ll int x,ll int res_size)
{
    ll int carry = 0;

    for (ll int i=0; i<res_size; i++)
    {
        ll int prod = res[i] * x + carry;
        res[i] = prod % 10;
        carry  = prod/10;
    }

    while (carry)
    {
        res[res_size] = carry%10;
        carry = carry/10;
        res_size++;
    }
    return res_size;
}


int main()
{
    ll int t,n,x,sq,mul,rs;
    sieve();
    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld",&n);
        memset(res,0,sizeof(res));
        memset(fact,0,sizeof(fact));
        for(ll int j=0; j<n; j++)
        {
            scanf("%lld",&x);
            sq=sqrt(x);

            for(ll int i=0; i<prime.size() and prime[i]<=sq; i++)
            {
                mul=prime[i];
                if(x%prime[i]==0)
                {
                    while(x%prime[i]==0)
                    {
                        mul=mul*prime[i];
                        x=x/prime[i];
                    }
                    mul=mul/prime[i];
                    fact[prime[i]]=max(fact[prime[i]],mul);
                }
            }
            if(x!=1)
            {
                fact[x]=max(fact[x],x);
            }
        }
        res[0]=1;
        rs=1;
        for(ll int i=1; i<=10000; i++)
        {
            if(fact[i]!=0)
            {
                rs=multiply(fact[i],rs);
            }
        }
        printf("Case %lld: ",ca);
        for(ll int i=rs-1; i>=0; i-- )
        {
            printf("%lld",res[i]);
        }
        printf("\n");
    }

}

10338 - Mischievous Children

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

Solution idea : factorial upto 20! can be easily stored into unsigned long long . ans is n! divided by the product of the factorials of equal characters.

Solution :

#include<bits/stdc++.h>
#define llu unsigned long long
using namespace std;

llu int fact[21];
llu int num[27];
char s[21];

int main()
{
    fact[0]=1;

    for(llu int i=1; i<21; i++)
    {
        fact[i]=fact[i-1]*i;
    }

    llu int t,l,res,ans,ca=1,val;

    scanf("%llu",&t);

    while(t--)
    {
        getchar();
        memset(num,0,sizeof(num));
        scanf("%s",s);
        l=strlen(s);

        for(llu int i=0; i<l; i++)
        {
            val=s[i]-'A';
            num[val]++;
        }
        res=1;

        for(llu int i=0; i<27; i++)
        {
            res=res*fact[num[i]];
        }
        ans=fact[l]/res;

        printf("Data set %llu: %llu\n",ca,ans);
        ca++;
    }

}

623 - 500!

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

Solution Idea : have to find factorial n with efficient method.

Solution :

#include<bits/stdc++.h>
#define ll long long
using namespace std;

#define MAX 10000

ll int res[MAX];

ll int multiply(ll int x,ll int res_size);

void factorial(ll int n)
{


    res[0] = 1;
    ll int res_size = 1;

    for (ll int x=2; x<=n; x++)
        res_size = multiply(x, res_size);


    for (ll int i=res_size-1; i>=0; i--)
        printf("%lld",res[i]);
        printf("\n");
}

ll int multiply(ll int x,ll int res_size)
{
   ll int carry = 0;

       for (ll int i=0; i<res_size; i++)
    {
        ll int prod = res[i] * x + carry;
        res[i] = prod % 10;
        carry  = prod/10;
    }

    while (carry)
    {
        res[res_size] = carry%10;
        carry = carry/10;
        res_size++;
    }
    return res_size;
}


int main()
{
    ll int n;

    while(scanf("%lld",&n)==1)
    {
        printf("%lld!\n",n);
        factorial(n);
    }

    return 0;

}

Factorial Finding Source code

Tutorial Link : http://www.geeksforgeeks.org/factorial-large-number/

Source Code :

#include<bits/stdc++.h>
#define ll long long
using namespace std;

#define MAX 800

ll int multiply(ll int x,ll int res[],ll int res_size);

void factorial(ll int n)
{
    ll int res[MAX];

    res[0] = 1;
    ll int res_size = 1;

    for (ll int x=2; x<=n; x++)
        res_size = multiply(x, res, res_size);

    cout << "Factorial of given number is \n";
    for (ll int i=res_size-1; i>=0; i--)
        cout << res[i];
}

ll int multiply(ll int x,ll int res[],ll int res_size)
{
   ll int carry = 0;

       for (ll int i=0; i<res_size; i++)
    {
        ll int prod = res[i] * x + carry;
        res[i] = prod % 10;
        carry  = prod/10;
    }

    while (carry)
    {
        res[res_size] = carry%10;
        carry = carry/10;
        res_size++;
    }
    return res_size;
}


int main()
{
    factorial(100);
    return 0;

}

324 - Factorial Frequencies

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

Solution Idea : have to calculate factorial of n and then iterate through it and find values.

Solution :

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

using namespace std;

 ll int res[MAX];
ll int a[10];
ll int multiply(ll int x,ll int res_size);

void factorial(ll int n)
{


    res[0] = 1;
    ll int res_size = 1;

    for (ll int x=2; x<=n; x++)
        res_size = multiply(x, res_size);

    for (ll int i=res_size-1; i>=0; i--)
        a[res[i]]++;
}

ll int multiply(ll int x,ll int res_size)
{
   ll int carry = 0;

       for (ll int i=0; i<res_size; i++)
    {
        ll int prod = res[i] * x + carry;
        res[i] = prod % 10;
        carry  = prod/10;
    }

    while (carry)
    {
        res[res_size] = carry%10;
        carry = carry/10;
        res_size++;
    }
    return res_size;
}


int main()
{

    ll int n;

  while(scanf("%lld",&n) and n)
    {
        memset(res,0,sizeof(res));
        memset(a,0,sizeof(a));

          factorial(n);

          printf("%lld! --\n",n);

          for(ll int i=0;i<=9;i++)
          {
             if(i!=4 and i!=9) printf("(%lld)    %lld    ",i,a[i]);
             else printf("(%lld)    %lld\n",i,a[i]);
          }
    }

}

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);

    }

}

1035 - Intelligent Factorial Factorization

Problem Link : http://lightoj.com/volume_showproblem.php?problem=1035

Solution Idea : Need to prime factorize n with faster factorial factorize method.

Solution :

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

using namespace std;

bool status[110];

vector<ll int>prime;

void sieve()
{
    int n=110;
    int sq=sqrt(n);

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

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

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

    prime.push_back(2);

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

void fact (ll int n )
{
    ll int ok=0;
    for ( ll int i = 0; i < prime.size() and prime[i]<= n; i++ )
    {
        ll int x = n;
        ll int freq = 0,c;

        while ( x / prime[i] )
        {
            freq += x / prime[i];
            x = x / prime[i];
        }

        if(ok==0)
        {

            printf("%lld (%lld)", prime[i], freq );
            ok++;
        }
        else
        {
            printf(" * ");
            printf("%lld (%lld)",prime[i],freq);

        }
    }
}
int main()
{
    sieve();

    ll int t,n;
    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld",&n);
        printf("Case %lld: %lld = ",ca,n);
        fact(n);
        printf("\n");
    }
}

Prime Factorization of Factorial Source code

Tutorial Link : http://blog.forthright48.com/2015/08/prime-factorization-of-factorial.html

Source Code :

#include<bits/stdc++.h>

using namespace std;

bool status[1100001];

vector<int>prime;

void sieve()
{
    int n=1000001;
    int sq=sqrt(n);

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

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

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

    prime.push_back(2);

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

void fact ( int n ) {
    for ( int i = 0; i < prime.size() and prime[i]<= n; i++ ) {
        int x = n;
        int freq = 0;

        while ( x / prime[i] ) {
            freq += x / prime[i];
            x = x / prime[i];
        }

        printf ( "%d^%d ", prime[i], freq );
    }
}
int main()
{
    sieve();

    int n;
    cin>>n;
    fact(n);

}