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

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;

}

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;

}

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

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;

}