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

    }

}