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

}