UVA - 10179 - Irreducable Basic Function

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

Explanation: Just use Euler's Phi function, also known as the totient function, is a function that, for a given positive integer , calculates the number of positive integers smaller than or equal to  that are relatively prime to . (Note that except when , only integers strictly smaller than  are counted, because .)

Code First Then See Solution


Code: 

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll phi(ll n)
{
    ll res=n;
    if(res%2==0)
    {
        while(res%2==0)
        {
            res/=2;
        }
        n-=n/2;
    }
    for(ll i=3;i*i<=res;i+=2)
    {
        if(res%i==0)
        {
            while(res%i==0)
                res/=i;
            n-=n/i;
        }
    }
    if(res>1)
        n-=n/res;
    return n;
}


int main()
{
   long long n;
   while(cin>>n)
   {
       if(n==0)
        break;
       ll ans=phi(n);
       cout<<ans<<endl;
   }
   return 0;
}

UVA - 10394 - Twin Primes

Problem link: https://onlinejudge.org/external/103/10394.pdf

Explanation: Precalculate all twin primes.




Code First Then See Solution 


Code: 

#include <bits/stdc++.h>

#define mx 20000009
#define ll long long

using namespace std;

long long int a[mx],b[mx];

int main()
{

    for(ll i=0;i<mx;i++)
        a[i]=0;
    a[0]=a[1]=1;
    for(ll i=4;i<mx;i+=2)
        a[i]=1;
    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;
        }
    }
    ll k=1;
    for(ll i=2;i<mx;i++)
    {
        if(a[i]==0&&a[i+2]==0)
            b[k++]=i;
    }
    ll s;
    while(cin>>s)
    {
        cout<<"("<<b[s]<<", "<<b[s]+2<<")"<<endl;
    }
    return 0;
}

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