SPOJ - ETF - Euler Totient Function


Problem Link: https://www.spoj.com/problems/ETF/en/



Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 1000002
int phi[mx];

int main()
{
    memset(phi,0,sizeof(phi));
    phi[1]=1;
    for(int i=2;i<=mx;i++)
    {

        if(phi[i]==0)
        {
            phi[i]=i-1;
            for(int j=i<<1;j<=mx;j+=i)
            {
                if(!phi[j])
                {
                    phi[j]=j;
                }
                phi[j]=(phi[j]/i)*(i-1);
                //cout<<phi[j]<<endl;
            }
        }
    }
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        cout<<phi[n]<<endl;
    }
    return 0;

}

SPOJ - DIVSUM2 - Divisor Summation (Hard)


Problem Link: https://www.spoj.com/problems/DIVSUM2/en/


Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 100000008
#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;
        }
    }
}


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

}

SPOJ - DIVSUM - Divisor Summation


Problem Link: https://www.spoj.com/problems/DIVSUM/en/

Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 500002

char a[mx];
vector <int> v;

void sieve()
{
    memset(a,0,sizeof(a));
    for(int i=4;i<=mx;i+=2)
        a[i]=1;
    for(int i=3;i<=sqrt(mx);i+=2)
    {
        if(a[i]==0)
        {
             for(int j=i*i;j<=mx;j+=i)
                a[j]=1;
        }

    }
    v.push_back(2);
    for(int i=3;i<mx;i+=2)
    {
        if(a[i]==0)
            v.push_back(i);
    }
}

int main()
{
    int t;
    sieve();
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int f=n;
        long long res=1;
        for(int i=0;v[i]<=sqrt(n);i++)
        {

            if(n%v[i]==0)
            {
                long long p=1,temp=1;
                while(n%v[i]==0)
                {
                    n/=v[i];
                    p*=v[i];
                    temp+=p;
                }
                res*=temp;
            }
        }
        if(n!=1)
        {
            res*=(1+n);
        }
        res-=f;
        cout<<res<<endl;
    }
    return 0;

}

LightOJ - 1214 - Large Division

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


Code: 

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t,l=0;
    cin>>t;
    while(t--)
    {
        l++;
        string str;
        long long n,m=0;
        cin>>str>>n;
        if(n<0)
            n*=-1;
        if(str[0]=='-')
        {
            for(int i=1;i<str.size();i++)
            {
                m=m*10+(str[i]-'0');
                m%=n;
            }
            if(m==0)
                cout<<"Case "<<l<<": divisible"<<endl;
            else
                cout<<"Case "<<l<<": not divisible"<<endl;
        }
        else
        {
           for(int i=0;i<str.size();i++)
            {
                m=m*10+(str[i]-'0');
                m%=n;
            }
            if(m==0)
                cout<<"Case "<<l<<": divisible"<<endl;
            else
                cout<<"Case "<<l<<": not divisible"<<endl;
        }
    }
    return 0;

}

LightOJ - 1138 - Trailing Zeroes (III)

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


Code: 

#include <bits/stdc++.h>

using namespace std;

long long zero(long long n)
{
    long long coun=0;
    while(n>=5)
    {
        coun+=n/5;
        n/=5;
    }
    return coun;
}

int main()
{
    int t,f=0;
    cin>>t;
    while(t--)
    {
        f++;
        long long n,low=1,high=6000000000000000000;
        cin>>n;
        long long res=-1;
        while(low<=high)
        {
            long long mid=(low+high)>>1;
            long long l=zero(mid);
            if(l==n)
            {
                res=mid;
                break;
            }
            else if(l>n)
            {
                high=mid-1;
            }
            else
            {
                low=mid+1;
            }
        }
        if(res==-1)
           cout<<"Case "<<f<<": "<<"impossible"<<endl;
        else
           cout<<"Case "<<f<<": "<<res-(res%5)<<endl;
    }
    return 0;
}

LightOJ - 1090 - Trailing Zeroes(II)


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


Code: 

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

int fact(int n, int k)
{
    //int f=n;
    int coun=0;
        while(n>=k)
        {
        coun+=n/k;
        n/=k;
        }
    return coun;
}

int poww(int n, int k)
{
    int coun=0;
    if(n%k==0)
    {
        while(n%k==0)
        {
            n/=k;
            coun++;
        }
    }
    return coun;
}

int main()
{
    int t,f=0;
    cin>>t;
    while(t--)
    {
        f++;
        int n,r,p,q;
        cin>>n>>r>>p>>q;
        int a1,a2,b1,b2,c1,c2;
        a1=fact(n,2);
       // cout<<"---"<<a1<<endl;
        a2=fact(n,5);
       // cout<<"---"<<a2<<endl;
        b1=fact(r,2);
       // cout<<"---"<<b1<<endl;
        b2=fact(r,5);
       // cout<<"---"<<b2<<endl;
        b1+=fact(n-r,2);
        b2+=fact(n-r,5);
        a1-=b1;
        a2-=b2;
        //a1=min(a1,a2);
        c1=poww(p,2);
        c1*=q;
        c2=poww(p,5);
        c2*=q;
        a1+=c1;
        a2+=c2;
        a1=min(a1,a2);
        cout<<"Case "<<f<<": "<<a1<<endl;
    }
    return 0;

}

LightOJ - 1035 - Intelligent Factorial Factorization

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


Code First Then See Solution

Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 150

char a[mx];
vector <int> v;

void sieve()
{
    memset(a,0,sizeof(a));
    for(int i=4;i<=mx;i+=2)
        a[i]=1;
    for(int i=3;i<=sqrt(mx);i++)
    {
        if(a[i]==0)
        {
            for(int j=i*i;j<=mx;j+=i)
                a[j]=1;
        }
    }
    v.push_back(2);
    for(int i=3;i<=mx;i+=2)
        if(a[i]==0)
           v.push_back(i);
}

int main()
{
    int t,m=0;
    cin>>t;
    sieve();
    while(t--)
    {
        m++;
       int n;
       cin>>n;
       cout<<"Case "<<m<<": "<<n<<" = ";
       int coun=0;
       vector <pair <int,int>> p;
       for(int i=0;v[i]<=n;i++)
       {
         int f=n;
         coun=0;
         while(f>=v[i])
         {
             f/=v[i];
             coun+=f;
         }
         p.push_back(make_pair(v[i],coun));
       }
       vector <pair <int,int>>:: iterator it;
       //int j=0;
       cout<<p[0].first<<" ("<<p[0].second<<")";
       for(int i=1;i<p.size();i++)
       {
          cout<<" * "<<p[i].first<<" ("<<p[i].second<<")";
       }
       cout<<endl;
    }
    return 0;

}