LightOJ - 1289 - LCM From 1 to n

Idea: LCM from 1 to n is the highest power of primes less than or equal to n.We can precalculate the primes.Use bitwise seive for generating Prime upto 10^8.

Code First Then See Solution

Code:
#include <bits/stdc++.h>

#define ll  unsigned

using namespace std;

const int MAX = 100000000;
const int LMT =     10000;

int _c[(MAX>>6)+1];

ll  p[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);

    p[x++]=2;
    mnt++;
    for (int i=3; i <= MAX; i += 2)
        if (!IsComp(i))
        {
            p[x++]=i;
            mnt++;
        }
}

ll store[5761482];

ll precal()
{
    store[0]=2;
    for(ll i=1;i<mnt;i++)
    {
        store[i]=store[i-1]*p[i];
    }
}

ll cal(ll n)
{
    ll temp,sum=1;
    ll x=sqrt(n);
    for(ll i=0;i<mnt&&p[i]<=x;i++)
    {
        temp=n;
        temp/=p[i];
        while(temp>=p[i])
        {
            temp/=p[i];
            sum*=p[i];
        }
    }
    return sum;
}

int main()
{
    int t,f=0;
    sieve();
    precal();
    cin>>t;
    while(t--)
    {
        f++;
        ll n,ans;
        cin>>n;
        ans=cal(n);
        ll u=upper_bound(p,p+mnt,n)-p;
        u--;
        ans*=store[u];
        cout<<"Case "<<f<<": "<<ans<<endl;
    }
    return 0;

}

Spoj -TDPRIMES - Printing some primes

Idea: Use Bitwise Seive.

Code First Then See Solution

Code:
#include <bits/stdc++.h>

using namespace std;
#define mx 100000000

int a[(mx>>5)+2];

bool status(int n,int pos)
{
    return bool(n&1<<pos);
}

int sett(int n,int pos)
{
    return n=n|(1<<pos);
}

int main()
{
    int n= 100000000;
    vector <int> v;
    for(int i=3;i<=sqrt(n);i+=2)
    {
        if(status(a[i>>5],i&31)==false)
        {
            for(int j=i*i;j<=n;j+=i)
            {
                a[j>>5]=sett(a[j>>5],j&31);
            }
        }
    }
    v.push_back(2);
    for(int i=3;i<=n;i+=2)
    {
        if(status(a[i>>5],i&31)==false)
            v.push_back(i);
    }
    for(int i=0;i<=v.size();i+=100)
        cout<<v[i]<<endl;
    return 0;
}

Spoj - LCMSUM - LCM Sum

Problem Link: https://www.spoj.com/problems/LCMSUM/

Idea : 

Code First Then See Solution

Code: 

#include <bits/stdc++.h>
using namespace std;

#define mx 1000008
#define ll long long

long long  a[mx+10];
long long res[mx+10];


void phi()
{
   memset(a,0,sizeof(a));
   a[1]=1;
   for(int i=2;i<=mx;i++)
   {
       if(a[i]==0)
       {
           a[i]=i-1;
           for(int j=i<<1;j<=mx;j+=i)
           {
               if(a[j]==0)
               {
                   a[j]=j;
               }
               a[j]=a[j]/i;
               a[j]*=(i-1);
           }
       }
   }
   //memset(res,0,sizeof(res));
   for(ll i=1;i<=mx;i++)
   {
       for(ll j=i;j<=mx;j+=i)
       {
           res[j]+=(i*a[i]);
       }
   }
}



int main()
{
    int t,f=0;
    //seive();
    phi();
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        long long sum=0;
        sum=res[n];
        sum++;
        sum*=n;
        sum/=2;
        cout<<sum<<endl;
    }
    return 0;
}

LightOJ - 1340 - Strory Of Tomisu Ghost

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

Idea :



Code First Then See Solution

 Code :

 #include <bits/stdc++.h>

using namespace std;

#define mx 100006
#define mod 10000019
#define ll long long

bitset <mx+10> b;
vector <ll> v;

void Seive()
{
    b.set();
    b[0]=b[1]=false;
    for(ll i=2;i<mx;i++)
    {
        if(b[i])
        {
            v.push_back(i);
            for(ll j=i*i;j<mx;j+=i)
                b[j]=false;
        }
    }
}

ll bigmod(ll a,ll c)
{
    if(c==0)
        return 1;
    if(c%2==0)
    {
        ll x=bigmod(a,c/2)%mod;
        return (x*x)%mod;
    }
    else
    {
        ll x=a%mod;
        ll y=bigmod(a,c-1)%mod;
        return (x*y)%mod;
    }
}

int main()
{
    int t,f=0;
    Seive();
    cin>>t;
    while(t--)
    {
        f++;
        ll n,t,res=1;
        cin>>n>>t;
        for(ll i=0;i<v.size()&&v[i]<=n;i++)
        {
            ll f=n,cnt=0;
            while(f>=v[i])
            {
               cnt+=f/v[i];
               f/=v[i];
            }
            if(cnt>=t)
            {
                cnt/=t;
                ll sum=bigmod(v[i],cnt);
                res=(res%mod*sum%mod)%mod;
            }
        }
        if(res==1)
            cout<<"Case "<<f<<": "<<"-1"<<endl;
        else
          cout<<"Case "<<f<<": "<<res<<endl;
    }
    return 0;
}

LightOJ - 1054 - Efficient Pseudo Code

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

Idea :We need find out the SOD value of n^m.If the prime factorization of n is,


p1^q1 * p2^q2 *.....*pn^qn then,
 sum of divisor = (1+p1+p1^2+..+p1^q1)*(1+p2+p2^2+..+p2^q2)*.....*(1+pn+pn^2+..+p1^qn)

to find p1^q1 there is a geometric equation,
   x=p1^(q1+1)-1/(p1-1)

but the value of p1^q1 is very large so we need to mod this value by 1000000007.We can easily do this by using BIGMOD.For p1-1 we need to find MODINVERSE of p1-1.Then multiply this value which is (p1-1)^-1 with  
p1^(q1+1)-1.


Code first Then See Solution

Code :

 #include <bits/stdc++.h>

using namespace std;

#define  mx 100006
#define mod 1000000007
#define ll long long

bitset <mx+10> b;
vector <ll> v;

void seive()
{
    b.set();
    b[0]=b[1]=false;
    for(ll i=2;i<mx;i++)
    {
        if(b[i])
        {
            v.push_back(i);
            for(ll j=i*i;j<mx;j+=i)
                b[j]=false;
        }
    }
}

ll bigmod(ll a,ll b)
{
   if(b==0)
        return 1;
   if(b%2==0)
   {
       ll x=bigmod(a,b/2)%mod;
       return (x*x)%mod;
   }
   else
   {
       ll x=a%mod;
       ll y=bigmod(a,b-1)%mod;
       return (x*y)%mod;
   }
}

ll modinverse(ll a)
{
    return bigmod(a,mod-2);
}

int main()
{
    int t,f=0;
    seive();
    cin>>t;
    while(t--)
    {
        f++;
        ll n,m,res1=1,res2=1,sum=1,s;
        cin>>n>>m;
        for(ll i=0;i<v.size()&&v[i]<=sqrt(n);i++)
        {
            if(n%v[i]==0)
            {
                ll cnt=0;
                while(n%v[i]==0)
                {
                    cnt++;
                    n/=v[i];
                }
                cnt*=m;
                cnt++;
                res1= bigmod(v[i],cnt);
                res2 = modinverse(v[i]-1);
                s=((res1-1+mod)%mod*(res2+mod%mod))%mod;
                sum=((sum%mod)*(s%mod))%mod;
                }
        }
        if(n>1)
        {
            ll cnt=m+1;
            res1=bigmod(n,cnt);
            res2 = modinverse(n-1);
            s=((res1-1+mod)%mod*(res2+mod)%mod)%mod;
            sum =((sum%mod)*(s%mod))%mod;
            }
        cout<<"Case "<<f<<": "<<sum<<endl;
    }
    return 0;
}

LightOJ - 1236 - Pairs Forming LCM


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

Idea :  Suppose x and y are two number and their LCM is n.

x= p1^a1*p2^a2*p3^a3......ps^a

y= p1^b1*p2^b2*p3^b3......ps^b3

n= p1^max(a1,b1)*p2^max(a2,b2)*p3^max(a3,b3)......ps^max(a3,b3)

The takes an ordered pair of numbers first. 1:ai=ci,bi=[0,ei] There are ei+1 species 2:bi=ci, Ai=[0,ei], and Ai==ci,bi==ci, the above appeared, so there is a 2*ei+1 species minus one. for unordered pairs, the Lcm (n,n) appears only once (EI==AI==BI) so the solution is: ((2*e1+1) * (2*e2+1) ... (2*es+1) +1)/2; for an example: n=2^3; when a1=3, b1=3,2,1,0; b1=3,a1=3,2,1,0; The considers the ordered pair time (3,3) to repeat once, so subtract one time. When multiple items are multiplied by the same time, use the multiplication rule.


Code First Then See Solution

Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 10000007
#define ll long long

bitset <mx>b;
vector <long long>v;

void seive()
{
    b.set();
    b[0]=b[1]=false;
    for(ll i=0;i<mx;i++)
    {
        if(b[i])
        {
            v.push_back(i);
            for(ll j=i*i;j<mx;j+=i)
                b[j]=false;
        }
    }
}

int main()
{
    int t,f=0;
    seive();
    cin>>t;
    while(t--)
    {
        f++;
        long long n,res=1;
        cin>>n;
        for(int i=0;i<v.size()&&v[i]<=n;i++)
        {
            if(n%v[i]==0)
            {
                int cnt=0;
                while(n%v[i]==0)
                {
                    cnt++;
                    n/=v[i];
                }
                res*=(2*cnt+1);
            }
        }
        if(n!=1)
            res*=(2*1+1);
        cout<<"Case "<<f<<": "<<res/2+1<<endl;
    }
    return 0;
}

 LightOJ - 1215 - Finding LCM

Ideas : LCM(a,b,c)= L ,here a, b, L are given and we have to find the value of c. LCM of two value is maximum power of their prime factorization.So,we need to prime factorize a,b, and L then compare their power if any prime factor power of L is greater than power of a and b  then it is from c.

Code First Then See Solutions

Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 1000007

#define ll long long

bitset <mx> b;

vector <ll> v;

void seive()

{

    b.set();

    b[0]=b[1]=false;

    for(ll i=0;i<mx;i++)

    {

        if(b[i])

        {

            v.push_back(i);

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

                b[j]=false;

        }

    }

}

int main()

{

    int t,f=0;

    seive();

    cin>>t;

    while(t--)

    {

        f++;

        long long a,b,l,gcd,lcm,res=1;

        cin>>a>>b>>l;

        if(l%a!=0||l%b!=0)

        {

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

           continue;

        }

        gcd=__gcd(a,b);

        lcm=(a*b)/gcd;

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

        {

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

            {

                int cnt1=0;

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

                {

                    cnt1++;

                    l/=v[i];

                }

                int cnt2=0;

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

                {

                    cnt2++;

                    lcm/=v[i];

                }

                if(cnt1>cnt2)

                {

                    for(int j=0;j<cnt1;j++)

                        res*=v[i];

                }

            }

        }

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

    }

    return 0;

}