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

        }

    }

}