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;

}

UVA - 11388 - GCD LCM



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

using namespace std;

int main()
{
    int q;
    cin>>q;
    while(q--)
    {
        long long g,l;
        cin>>g>>l;
        if(l<g)
            swap(g,l);
        if(l%g==0)
            cout<<g<<" "<<l<<endl;
        else
            cout<<"-1"<<endl;
    }
    return 0;

}

SPOJ - NDIV - n-divisors

Idea: Find Out the number of divisors(NOD) using prime factorization.Use Seive for finding prime number upto sqrt(10^9).

Code First Then See Solution

Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 3200

int a[mx+10];
vector <int> v;

void seive()
{
   memset(a,0,sizeof(a));
   for(int i=2;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 a,b,n;
    seive();
    cin>>a>>b>>n;
    int res=0,sum;
    for(int i=a;i<=b;i++)
    {
        int temp=i;
        sum=1;
        for(int j=0;j<v.size()&&v[j]<=sqrt(temp);j++)
        {
            if(temp%v[j]==0)
            {
                int cnt=0;
                while(temp%v[j]==0)
                {
                    cnt++;
                    temp/=v[j];
                }
                sum*=(cnt+1);
            }
        }
        if(temp!=1)
        {
            sum*=2;
        }
        if(sum==n)
            res++;
    }
    cout<<res<<endl;
    return 0;

}

UVA - 10484 - Divisibility Of Factors

Problem Link: https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1425

Idea: If some number a is divisible by d.Then we could say that, if a = p^i*q^j  and d=p^r*q^f then i and j must be greater or equal ofr and f respectively.So, we have to prime factorize the number given n.Then check if each prime number which are in n is greater or less with compare to prime factors of m.if power of prime factors of m is greater than n ,the answer is zero. Otherwise, multiplication of powers of each factor of n is the answer.

If n is 0 then answer depens on m.if m is 1 than answer is one.


Code First Then See Solution


Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 110
#define ll long long

int a[mx+10];
vector <int> v;

void seive()
{
    memset(a,0,sizeof(a));
    for(int i=2;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()
{
    ll n,m;
    seive();
    while(cin>>n>>m)
    {
        if(n==0&&m==0)
            break;
        if(m<0)
        m*=(-1);
        if(n==0)
          {
              if(m==1)
              {
                cout<<1<<endl;
                continue;
              }
              else
              {
                cout<<0<<endl;
                continue;
              }

          }
        int b[110];
        memset(b,0,sizeof(b));
        int k=0;
        for(int i=0;i<v.size()&&v[i]<=n;i++)
        {
            int f=n,cnt=0;
            while(f>=v[i])
            {
                cnt+=f/v[i];
                f/=v[i];
            }
            if(cnt>0)
            b[v[i]]=cnt;
        }
        ll res=1;
        for(int i=0;i<v.size()&&m>=v[i];i++)
        {
            if(m%v[i]==0)
            {
                int cn=0;
                while(m%v[i]==0)
                {
                    cn++;
                    m/=v[i];
                    b[v[i]]--;
                    if(b[v[i]]<0)
                    {
                        res=0;
                        break;
                    }
                }
                if(res==0)
                    break;
            }
        }

        if(m!=1)
            res=0;

        for(int i=0;i<101;i++)
        {
            if(b[i]!=0)
              res*=(b[i]+1);
        }
        cout<<res<<endl;
    }
    return 0;

}

Spoj - FACT0- Integer Factorization

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

Idea : Simple Prime factorization problem.Do not use Sieve or you will get TLE.

Code First Then See Solution

Code:

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main()

{

    ll n;

    while(cin>>n)

    {

        if(n==0)

            break;

        ll cnt=0;

        while(n%2==0)

        {

            cnt++;

            n/=2;

        }

        if(cnt>0)

            cout<<"2"<<"^"<<cnt<<" ";

        ll x=3;

        while(x*x<=n)

        {

            cnt=0;

            while(n%x==0)

            {

                cnt++;

                n/=x;

            }

            if(cnt>0)

                cout<<x<<"^"<<cnt<<" ";

            x+=2;

        }

        if(n!=1)

            cout<<n<<"^"<<1<<endl;

        else

            cout<<endl;

    }

    return 0;

}

UVAOJ - 11064 - Number Theory

Problem Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2005

Idea: Phi value of a number is the total value that make GCD=1, with the number n.The divisors are the numbers that make GCD of the number n.
So,
      total value = n - phi(n) - number of divisors of n.


Code First Then See Sloution

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

using namespace std;

#define ll long long

#define mx 1000789

char a[mx+6];
int phi[mx+6];
vector <ll> v;


void seive()
{
    memset(a,0,sizeof(a));
    for(ll i=3;i<=sqrt(mx);i+=2)
    {
        if(a[i]==0)
        {
            for(ll 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()
{
    ll n;
    seive();
    while(cin>>n)
    {
        ll t=n,sum=1,k=n;
        if(n==1||n==2)
        {
            cout<<0<<endl;
            continue;
        }
        for(int 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];
                }
                t=(t/v[i])*(v[i]-1);
                sum*=(cnt+1);
            }
        }
        if(n>1)
        {
            sum*=2;
            t=(t/n)*(n-1);
        }
        sum--;
      cout<<k-sum-t<<endl;
    }
    return 0;
}

CodeForces -  k-rounding

Problem Link: https://codeforces.com/problemset/problem/858/A

Idea: 

Code First Then See Solution

Code: 

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int main()
{
    ll n,sum=1;
    int k;
    cin>>n>>k;
    int cnt2=0,cnt5=0;
    ll f=n;
    while(f%2==0)
    {
        cnt2++;
        f/=2;
    }
    f=n;
     while(f%5==0)
    {
        cnt5++;
        f/=5;
    }
    cnt2=max(k-cnt2,0);
    cnt5=max(k-cnt5,0);
    for(ll i=0;i<cnt2;i++)
        sum*=2;
    for(ll i=0;i<cnt5;i++)
        sum*=5;
    cout<<sum*n<<endl;
    return 0;

}

UVAOJ - 10680 - LCM

Problem Link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1621


Idea: The idea is simple if we want to calculate the LCM for the numbers of 

1,2,3,⋯,n we first list all the prime factors between [1,n]. For each factor in that list we need the maximum exponent such that px≤n. In other words, let's say that n=20 we want to know the highest power of 2 in the LCM(1,2,⋯,20) we can try the following:

21≤20 (true)

22≤20 (true)

23≤20 (true)

24≤20 (true)

25≤20 (false)

So the largest power of 2 in the LCM(1,2,⋯,20) is 24.

We repeat this process for the other prime factor in the range [1,n]. After that for each prime factor we calculate the answer mod 10. To avoid getting 0's at the end we subtract the cnt2−cnt5, because between 1,2,3,⋯,n always there is going to be more factors of two than factors of five, this subtraction is always going to be greater than 0.

Code First Then See Solution
Code: 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

bool a[1000397];
vector <int> v;
int mx=1000356;

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

int main()
{
    ll n;
    sieve();
    while(cin>>n)
    {
        if(n==0)
            break;
        ll sum=1;
        ll cnt2=0,cnt5=0;
        for(ll i=2;i<=n;i*=2)
          cnt2++;
        for(ll i=5;i<=n;i*=5)
          cnt5++;
        for(ll i=0;i<cnt2-cnt5;i++)
        {
            sum*=2;
            sum%=10;
        }
        for(int i=2;i<v.size()&&v[i]<=n;i++)
        {
            for(ll j=v[i];j<=n;j*=v[i])
            {
                sum*=v[i];
                sum%=10;
            }
        }
         cout<<sum<<endl;
    }
    return 0;

}