LightOJ 1028 - Trailing Zeroes (I)

LightOJ 1028 - Trailing Zeroes (I)

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

Ideas : Trailing Zeros in different base means if the base number divide the number or not.Suppose we have a number 12.We find the number of bases where trailing zero exists.

 12  base 2 = 1100 --trailing zero exists.

 12 base 3 = 110 -- trailing zero exists

 12 base 4  = 030 --trailing zero exists

 12 base 5 = 022 --trailing zero doesn't exists

 12 base 6 = 020 -- trailing zero exists

 12 base 7 = 015 --trailing doesn't zero exists

Here, we see that the base that divides the number has trailing zeros.So, the problem is very simple.We have to find out the number of divisors.

If a number, N=p1^a1*p2^a2*p3^a3  then Number of divisors = (a1+1)*(a2+1)*(a3+1).

Code first then see solution if needed

Code:

#include <bits/stdc++.h>

using namespace std;

#define mx 1000010

bool a[mx+10];

vector <int> v;

void sieve()

{

    memset(a,true,sizeof(a));

    for(int i=4;i<=mx;i+=2)

    {

        a[i]=false;

    }

    for(int i=3;i<=sqrt(mx);i+=2)

    {

        if(a[i]==true)

        {

            for(int j=i*i;j<=mx;j+=i)

                a[j]=false;

        }

    }

    v.push_back(2);

    for(int i=3;i<mx;i+=2)

       if(a[i]==true)

         v.push_back(i);

}

int main()

{

    int t,f=0;

    sieve();

    cin>>t;

    while(t--)

    {

        f++;

        long long n,l;

        cin>>n;

        l=sqrt(n);

        long long ans=1;

        for(long long i=0;v[i]<=l&&i<v.size();i++)

        {

            if(n%v[i]==0)

            {

                int coun=0;

                while(n%v[i]==0)

                {

                    n/=v[i];

                    coun++;

                }

                l=sqrt(n);

                ans*=(coun+1);

            }

        }

        if(n>1)

            ans*=2;

        ans--;

        cout<<"Case "<<f<<": "<<ans<<endl;

    }

    return 0;

}