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

}