1138 - Trailing Zeroes (III)

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

Solution idea : binary search problem..take any number and find how many trailing zeros are in it...compare it with required number and continue the process.

Solution :

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

ll int fact ( ll int n,ll int p  )
{

    ll int x = n;
    ll int freq = 0;

    while ( x / p )
    {
        freq += x / p;
        x = x / p;
    }


    return freq;
}

ll int func(ll int n)
{
    ll int hi=1000000000000000000,lo=0,mid,ans,a1,a2,w=-1;

    while(lo<=hi)
    {
        mid=(lo+hi)/2;

        a1=fact(mid,2);
        a2=fact(mid,5);
        a1=min(a1,a2);

        if(a1==n)
        {
            hi=mid-1;
            ans=mid;
            w=0;
        }
        else if(a1>n)
        {
            hi=mid-1;
        }
        else lo=mid+1;
    }
    if(w==0) return ans;
    else return -1;
}

int main()
{
    ll int t,n,ans;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld",&n);
        ans=func(n);

        if(ans==-1) printf("Case %lld: impossible\n",ca);
        else printf("Case %lld: %lld\n",ca,ans);

    }
}

1138 - Trailing Zeroes (III)

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

Solution idea : binary search problem..take any number and find how many trailing zeros are in it...compare it with required number and continue the process.

Solution :

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

ll int fact ( ll int n,ll int p  )
{

    ll int x = n;
    ll int freq = 0;

    while ( x / p )
    {
        freq += x / p;
        x = x / p;
    }


    return freq;
}

ll int func(ll int n)
{
    ll int hi=1000000000000000000,lo=0,mid,ans,a1,a2,w=-1;

    while(lo<=hi)
    {
        mid=(lo+hi)/2;

        a1=fact(mid,2);
        a2=fact(mid,5);
        a1=min(a1,a2);

        if(a1==n)
        {
            hi=mid-1;
            ans=mid;
            w=0;
        }
        else if(a1>n)
        {
            hi=mid-1;
        }
        else lo=mid+1;
    }
    if(w==0) return ans;
    else return -1;
}

int main()
{
    ll int t,n,ans;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld",&n);
        ans=func(n);

        if(ans==-1) printf("Case %lld: impossible\n",ca);
        else printf("Case %lld: %lld\n",ca,ans);

    }
}

1090 - Trailing Zeroes (II)

Problem Link :

Solution Idea : Interesting one. we have to find the number of 2's and number of 5's in (nCr*p^q). the ans is min(total number of 2's,total number of 5's).

Solution :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll int fact ( ll int n,ll int p  )
{

    ll int x = n;
    ll int freq = 0;

    while ( x / p )
    {
        freq += x / p;
        x = x / p;
    }


    return freq;
}

ll int fcnt(ll int n,ll int m)
{
    ll int cnt=0;

    while(n>0 and !(n%m))
    {
        n=n/m;
        cnt++;
    }
    return cnt;
}

int main()
{
    ll int t,n,r,p,q,a1,a2,a3,b1,b2,cnt,b3;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld%lld%lld%lld",&n,&r,&p,&q);
        cnt=0;
        a1=fact(n,2);
        b1=fact(n,5);
        a2=fact(r,2);
        b2=fact(r,5);
        a3=fact(n-r,2);
        b3=fact(n-r,5);
        a1=a1-(a2+a3);
        b1=b1-(b2+b3);


        a2=fcnt(p,2)*q;
        b2=fcnt(p,5)*q;

        a3=a1+a2;
        b3=b1+b2;

        a1=min(a3,b3);

        printf("Case %lld: %lld\n",ca,a1);

    }

}

1028 - Trailing Zeroes (I)

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

Solution Idea : number of divisors

Solution :

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

bool status[1000009];

vector<ll int>prime;

void sieve()
{
    ll int n=1000000;
    ll int sq=sqrt(n);

    prime.push_back(2);

    for(int i=4;i<=n;i=i+2) status[i]=1;

    for(int i=3;i<=sq;i=i+2)
    {
        if(status[i]==0)
        {
                   for(int j=i*i;j<=n;j=j+i)
            {
                status[j]=1;
            }
        }
    }
    status[1]=1;
    status[0]=1;

    for(ll int i=3;i<=n;i=i+2)
    {
        if(status[i]==0)      prime.push_back(i);
    }
}

ll int nod(ll int n)
{
    ll int sq=sqrt(n);
    ll int res=1;

    for(int i=0;i<prime.size() && prime[i]<=sq;i++)
    {
        int cnt=1;
  int c=prime[i];
        while(n%prime[i]==0)
        {
            n=n/prime[i];
            cnt++;
        }
        sq=sqrt(n);

        res= res*(cnt);
    }
    if(n!=1)
    {
        res=res*2;
    }
    return res;
}

int main()
{
    sieve();
   ll int t,n,ans;
   scanf("%lld",&t);

   for(ll int ca=1;ca<=t;ca++)
   {
       scanf("%lld",&n);
       ans=nod(n);
       ans--;
       printf("Case %lld: %lld\n",ca,ans);
   }

}

1067 - Combinations

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

Solution Idea : ans is nCr. which is n!/r!(n-r)! .  as n and k is below <=10^6. so first we store the value of factorial 1 to 10^6 mod 1000003 in fact array.

then for finding n!/r!(n-r)! we need to find the modular inverse of r!(n-r)!. then ans is( n! * modular inverse of r!(n-r)!) mod 1000003.

Solution :

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll int X=-1,Y=-1;

ll int ext_gcd ( ll int A,ll int B)
{
    ll int x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1;
    y2 = 0;
    x1 = 0;
    y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y )
    {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    X = x2;
    Y = y2;

    return r2;
}

ll int minv(ll int a,ll int m)
{
    ext_gcd(a,m);

    X=X%m;

    if(X<0) X=X+m;

    return X;
}


ll int fact[1000001];
ll int m=1000003;

int main()
{
    fact[0]=1;

    for(ll int i=1; i<=1000000; i++)
    {
        fact[i]=((fact[i-1]%m)*(i%m))%m;
    }

    ll int t,n,r,ans;

    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld%lld",&n,&r);

        ans= ((fact[r]%m)*(fact[n-r]%m))%m;
        ans=minv(ans,m);
        ans=(fact[n]*ans)%m;
        printf("Case %lld: %lld\n",ca,ans);
    }

}

1214 - Large Division

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

Solution Idea : manual division.

Solution :

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

char s[10002];

int main()
{

    ll int b,t,sz,res,val,p,cnt,i,w;

    scanf("%lld",&t);
    getchar();
    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%s%lld",s,&b);
        getchar();

        if(b<0) b=-1*b;

        p=b,cnt=0,res=-1,val=0,i=0,w=-1;

        sz=strlen(s);
        if(s[0]=='-')i++;
        val=s[i]-48;
        while(i<sz)
        {
            if(val>=b)
            {
                val=val%b;
                i++;
                w=0;
            }

            else
            {
                i++;
                if(w==0)
                {
                    i--;
                    w=-1;
                }
                if(i<sz )
                {
                    val=(val*10)+s[i]-48;

                }
            }

        }
        if(val==0)
        {
            printf("Case %lld: divisible\n",ca);
        }
        else printf("Case %lld: not divisible\n",ca);
    }


}

10176 - Ocean Deep! - Make it shallow!!

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

Solution idea : take every digit and represent it in decimal and mod it.. update the result every time...if the final result is divisible by m than ans is YES.

Solution : 

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

ll int bigmod(ll int b,ll int p,ll int m)
{
    if(p==0) return 1%m;

    else if(p%2==0)
    {
        ll int y= bigmod(b,p/2,m);

        return (y*y)%m;
    }
    else return (b*(bigmod(b,p-1,m)))%m;
}

ll int s[10002];

int main()
{
    char ch;
    ll int index,m=131071,res,val;

    while(scanf("%ch",&ch)==1)
    {
        index=0;
        s[index]=ch-48;
        index++;
        res=0;
        val=0;
        while(scanf("%ch",&ch)==1)
        {
            if(ch=='#') break;
            if(ch=='1'||ch=='0')
            {
                s[index]=ch-48;
                index++;
            }

        }
        getchar();
        for(ll int i=0; i<index; i++)
        {
            val=(s[i]*bigmod(2,index-1-i,m))%m;
            res=res+val;
        }
        if(res%m==0) printf("YES\n");
        else printf("NO\n");
    }

}

Modular Inverse source code

Tutorial Link : http://blog.forthright48.com/2015/09/modular-multiplicative-inverse.html

Code : 

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll int X=-1,Y=-1;

ll int ext_gcd ( ll int A,ll int B){
    ll int x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1; y2 = 0;
    x1 = 0; y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    X = x2;
    Y = y2;

    return r2;
}

ll int minv(ll int a,ll int m)
{
    ext_gcd(a,m);

    X=X%m;

    if(X<0) X=X+m;

    return X;
}

int main()
{
    ll int a,m;
    scanf("%lld%lld",&a,&m);

    printf("%lld",minv(a,m));

}

Bigmod recursive method source code

Tutorial Link : http://blog.forthright48.com/2015/08/modular-exponentiation.htm

Code :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll int bigmod(ll int b,ll int p,ll int m)
{
    if(p==0) return 1%m;

    else if(p%2==0)
    {
        ll int y= bigmod(b,p/2,m);

        return (y*y)%m;
    }
    else return (b*(bigmod(b,p-1,m)))%m;
}

int main()
{
 ll int b,p,m;

 scanf("%lld%lld%lld",&b,&p,&m);

 printf("%lld",bigmod(b,p,m));


}

1024 - Eid

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

Solution Idea : it's visible that ans is the lcm of all numbers given. but the ans can be very big. so we need to calculate the lcm in efficient way and store the result into an array.

Solution :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

bool status[10002];

vector<ll int>prime;

void sieve()
{
    ll int n=10000;
    ll int sq=sqrt(n);

    for(ll int i=4; i<=n; i=i+2) status[i]=true;

    prime.push_back(2);

    for(ll int i=3; i<=sq; i=i+2)
    {
        if(status[i]==false)
        {
            for(int j=i*i; j<=n; j=j+i) status[j]=true;
        }
    }
    status[1]=1;
    status[0]=1;

    for(ll int i=3; i<=n; i=i+2)
    {
        if(status[i]==0) prime.push_back(i);
    }
}
ll int res[1000000];
ll int fact[10001];
ll int multiply(ll int x,ll int res_size)
{
    ll int carry = 0;

    for (ll int i=0; i<res_size; i++)
    {
        ll int prod = res[i] * x + carry;
        res[i] = prod % 10;
        carry  = prod/10;
    }

    while (carry)
    {
        res[res_size] = carry%10;
        carry = carry/10;
        res_size++;
    }
    return res_size;
}


int main()
{
    ll int t,n,x,sq,mul,rs;
    sieve();
    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld",&n);
        memset(res,0,sizeof(res));
        memset(fact,0,sizeof(fact));
        for(ll int j=0; j<n; j++)
        {
            scanf("%lld",&x);
            sq=sqrt(x);

            for(ll int i=0; i<prime.size() and prime[i]<=sq; i++)
            {
                mul=prime[i];
                if(x%prime[i]==0)
                {
                    while(x%prime[i]==0)
                    {
                        mul=mul*prime[i];
                        x=x/prime[i];
                    }
                    mul=mul/prime[i];
                    fact[prime[i]]=max(fact[prime[i]],mul);
                }
            }
            if(x!=1)
            {
                fact[x]=max(fact[x],x);
            }
        }
        res[0]=1;
        rs=1;
        for(ll int i=1; i<=10000; i++)
        {
            if(fact[i]!=0)
            {
                rs=multiply(fact[i],rs);
            }
        }
        printf("Case %lld: ",ca);
        for(ll int i=rs-1; i>=0; i-- )
        {
            printf("%lld",res[i]);
        }
        printf("\n");
    }

}

10338 - Mischievous Children

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

Solution idea : factorial upto 20! can be easily stored into unsigned long long . ans is n! divided by the product of the factorials of equal characters.

Solution :

#include<bits/stdc++.h>
#define llu unsigned long long
using namespace std;

llu int fact[21];
llu int num[27];
char s[21];

int main()
{
    fact[0]=1;

    for(llu int i=1; i<21; i++)
    {
        fact[i]=fact[i-1]*i;
    }

    llu int t,l,res,ans,ca=1,val;

    scanf("%llu",&t);

    while(t--)
    {
        getchar();
        memset(num,0,sizeof(num));
        scanf("%s",s);
        l=strlen(s);

        for(llu int i=0; i<l; i++)
        {
            val=s[i]-'A';
            num[val]++;
        }
        res=1;

        for(llu int i=0; i<27; i++)
        {
            res=res*fact[num[i]];
        }
        ans=fact[l]/res;

        printf("Data set %llu: %llu\n",ca,ans);
        ca++;
    }

}

623 - 500!

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

Solution Idea : have to find factorial n with efficient method.

Solution :

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

#define MAX 10000

ll int res[MAX];

ll int multiply(ll int x,ll int res_size);

void factorial(ll int n)
{


    res[0] = 1;
    ll int res_size = 1;

    for (ll int x=2; x<=n; x++)
        res_size = multiply(x, res_size);


    for (ll int i=res_size-1; i>=0; i--)
        printf("%lld",res[i]);
        printf("\n");
}

ll int multiply(ll int x,ll int res_size)
{
   ll int carry = 0;

       for (ll int i=0; i<res_size; i++)
    {
        ll int prod = res[i] * x + carry;
        res[i] = prod % 10;
        carry  = prod/10;
    }

    while (carry)
    {
        res[res_size] = carry%10;
        carry = carry/10;
        res_size++;
    }
    return res_size;
}


int main()
{
    ll int n;

    while(scanf("%lld",&n)==1)
    {
        printf("%lld!\n",n);
        factorial(n);
    }

    return 0;

}

Factorial Finding Source code

Tutorial Link : http://www.geeksforgeeks.org/factorial-large-number/

Source Code :

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

#define MAX 800

ll int multiply(ll int x,ll int res[],ll int res_size);

void factorial(ll int n)
{
    ll int res[MAX];

    res[0] = 1;
    ll int res_size = 1;

    for (ll int x=2; x<=n; x++)
        res_size = multiply(x, res, res_size);

    cout << "Factorial of given number is \n";
    for (ll int i=res_size-1; i>=0; i--)
        cout << res[i];
}

ll int multiply(ll int x,ll int res[],ll int res_size)
{
   ll int carry = 0;

       for (ll int i=0; i<res_size; i++)
    {
        ll int prod = res[i] * x + carry;
        res[i] = prod % 10;
        carry  = prod/10;
    }

    while (carry)
    {
        res[res_size] = carry%10;
        carry = carry/10;
        res_size++;
    }
    return res_size;
}


int main()
{
    factorial(100);
    return 0;

}

324 - Factorial Frequencies

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

Solution Idea : have to calculate factorial of n and then iterate through it and find values.

Solution :

#include<bits/stdc++.h>
#define ll long long
#define MAX 800

using namespace std;

 ll int res[MAX];
ll int a[10];
ll int multiply(ll int x,ll int res_size);

void factorial(ll int n)
{


    res[0] = 1;
    ll int res_size = 1;

    for (ll int x=2; x<=n; x++)
        res_size = multiply(x, res_size);

    for (ll int i=res_size-1; i>=0; i--)
        a[res[i]]++;
}

ll int multiply(ll int x,ll int res_size)
{
   ll int carry = 0;

       for (ll int i=0; i<res_size; i++)
    {
        ll int prod = res[i] * x + carry;
        res[i] = prod % 10;
        carry  = prod/10;
    }

    while (carry)
    {
        res[res_size] = carry%10;
        carry = carry/10;
        res_size++;
    }
    return res_size;
}


int main()
{

    ll int n;

  while(scanf("%lld",&n) and n)
    {
        memset(res,0,sizeof(res));
        memset(a,0,sizeof(a));

          factorial(n);

          printf("%lld! --\n",n);

          for(ll int i=0;i<=9;i++)
          {
             if(i!=4 and i!=9) printf("(%lld)    %lld    ",i,a[i]);
             else printf("(%lld)    %lld\n",i,a[i]);
          }
    }

}

10139 - Factovisors

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

Solution Idea : m will divide n! if all the prime factors of m have equal or less power than the power of that prime number in n!. if m==1 than ans is true and m==0 ans is false.
so for this we have to prime factorize m first. then for every prime factor of m we need to check how many times it occurs in n! with proper function.

Solution :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

bool status[46400];
ll int a[46400];
ll int global=0;

vector<ll int>prime;

void sieve()
{
    ll int n=46380;
    ll int sq=sqrt(n);

    prime.push_back(2);

    for(ll int i=4; i<=n; i=i+2) status[i]=1;

    for(ll int i=3; i<=sq; i=i+2)
    {
        if(status[i]==0)
        {


            for(ll int j=i*i; j<=n; j=j+i)
            {
                status[j]=1;
            }
        }
    }
    status[1]=1;
    status[0]=1;

    for(ll int i=3; i<=n; i=i+2)
    {
        if(status[i]==0) prime.push_back(i);
    }
}

void nod(ll int n)
{
    ll int sq=sqrt(n);
    ll int res=1;

    for(ll int i=0; i<prime.size() && prime[i]<=sq; i++)
    {

        if(n%prime[i]==0)
        {
            while(n%prime[i]==0)
            {
                n=n/prime[i];
                a[prime[i]]++;
            }
            sq=sqrt(n);


        }
    }
    if(n!=1)
    {
        global=n;
    }

}
ll int  fact( ll int  n, ll int p )
{
    ll int  freq = 0;
    ll int x = n;

    while ( x )
    {
        freq += x / p;
        x = x / p;
    }

    return freq;
}

int main()
{
    ll int n,m,val,w,ca,cnt;
    sieve();

    while(scanf("%lld%lld",&n,&m)==2)
    {
        memset(a,0,sizeof(a));
        w=0;
        global=0;
        cnt=0;
        if(m==1 )
        {
            printf("%lld divides %lld!\n",m,n);
            continue;
        }
        nod(m);
        for(ll int i=0; i<prime.size() and prime[i]<=m; i++)
        {
            val=fact(n,prime[i]);

            ca=a[prime[i]];
            if(val>=ca)
            {
                if(val>0 and ca>0) cnt++;
            }
            else
            {
                w=1;
                break;
            }
        }
        if( w==0 and global!=0)
        {
            if(fact(n,global)>0)
            {
                printf("%lld divides %lld!\n",m,n);
                w=-5;
            }
            else w=3;
        }
        if((w==1 || cnt==0)and w!=-5)printf("%lld does not divide %lld!\n",m,n);
        else if(w==3) printf("%lld does not divide %lld!\n",m,n);
        else if(w==0) printf("%lld divides %lld!\n",m,n);

    }

}

1035 - Intelligent Factorial Factorization

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

Solution Idea : Need to prime factorize n with faster factorial factorize method.

Solution :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

bool status[110];

vector<ll int>prime;

void sieve()
{
    int n=110;
    int sq=sqrt(n);

    for(int i=4; i<=n; i=i+2) status[i]=true;

    for(int i=3; i<=sq; i=i+2)
    {
        if(status[i]==false)
        {

            for(int j=i*i; j<=n; j=j+i) status[j]=true;
        }
    }
    status[1]=1;
    status[0]=1;

    prime.push_back(2);

    for(int i=3; i<=n; i=i+2)
    {
        if(status[i]==0) prime.push_back(i);
    }
}

void fact (ll int n )
{
    ll int ok=0;
    for ( ll int i = 0; i < prime.size() and prime[i]<= n; i++ )
    {
        ll int x = n;
        ll int freq = 0,c;

        while ( x / prime[i] )
        {
            freq += x / prime[i];
            x = x / prime[i];
        }

        if(ok==0)
        {

            printf("%lld (%lld)", prime[i], freq );
            ok++;
        }
        else
        {
            printf(" * ");
            printf("%lld (%lld)",prime[i],freq);

        }
    }
}
int main()
{
    sieve();

    ll int t,n;
    scanf("%lld",&t);

    for(ll int ca=1; ca<=t; ca++)
    {
        scanf("%lld",&n);
        printf("Case %lld: %lld = ",ca,n);
        fact(n);
        printf("\n");
    }
}

Prime Factorization of Factorial Source code

Tutorial Link : http://blog.forthright48.com/2015/08/prime-factorization-of-factorial.html

Source Code :

#include<bits/stdc++.h>

using namespace std;

bool status[1100001];

vector<int>prime;

void sieve()
{
    int n=1000001;
    int sq=sqrt(n);

    for(int i=4;i<=n;i=i+2) status[i]=true;

    for(int i=3;i<=sq;i=i+2)
    {
        if(status[i]==false)
        {

            for(int j=i*i;j<=n;j=j+i) status[j]=true;
        }
    }
    status[1]=1;
    status[0]=1;

    prime.push_back(2);

    for(int i=3;i<=n;i=i+2)
    {
        if(status[i]==0) prime.push_back(i);
    }
}

void fact ( int n ) {
    for ( int i = 0; i < prime.size() and prime[i]<= n; i++ ) {
        int x = n;
        int freq = 0;

        while ( x / prime[i] ) {
            freq += x / prime[i];
            x = x / prime[i];
        }

        printf ( "%d^%d ", prime[i], freq );
    }
}
int main()
{
    sieve();

    int n;
    cin>>n;
    fact(n);

}

10090 - Marbles

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

Solution Idea : A very good problem. we have to use extended euclid and then the  solve  of Diophantine equation with positive values to solve this problem.for avoiding tle we need to check only the boundary values of the limit for the positive solution.

Solution :

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


ll int X=-1,Y=-1;

ll int ext_gcd (ll int A,ll int B)
{
    ll int x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1;
    y2 = 0;
    x1 = 0;
    y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y )
    {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    X = x2;
    Y = y2;

    return r2;
}

int main()
{
    ll int n,c1,n1,c2,n2,g,x1,y1,x,y,lo,hi,ans=1000000000000000,m=1000000000000000,a1=0,b1=0;

    while(scanf("%lld",&n) and n)
    {
        scanf("%lld%lld%lld%lld",&c1,&n1,&c2,&n2);
        ans=1000000000000000;
        m=1000000000000000;
        g=ext_gcd(n1,n2);

        if(n%g!=0) printf("failed\n");
        else
        {
            x=(n*X)/g;
            y=(n*Y)/g;

            lo=ceil(-((double)n*X)/n2);
            hi=floor(((double)n*Y)/n1);

            if(lo>hi)
            {
                printf("failed\n");
                continue;
            }

            x1=x+((n2*lo)/g);
            y1=y-((n1*lo)/g);
            a1=x+((n2*hi)/g);
            b1=y-((n1*hi)/g);

            if(x1>=0 and y1>=0)
            {


                m=(x1*c1)+(y1*c2);
            }
            if(a1>=0 and b1>=0)
            {


                ans =(a1*c1)+(b1*c2);
            }
            if(m<ans)
            {
                ans=m;
                a1=x1;
                b1=y1;
            }

            printf("%lld %lld\n",a1,b1);
        }
    }



}

10673 - Play with Floor and Ceil

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

Solution idea : Extended euclid.

Solution :

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

using namespace std;


ll int X=-1,Y=-1;

ll int ext_gcd ( ll int A, ll int B){
    ll int x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1; y2 = 0;
    x1 = 0; y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    X = x2;
    Y = y2;

    return r2;
}

int main()
{
    ll int x,k,a,b,t,g,x1,y1;

    scanf("%lld",&t);

    while(t--)
    {
        scanf("%lld%lld",&x,&k);
        a=floor((double)x/k);
        b=ceil((double)x/k);

        g=ext_gcd(a,b);

        x1=(x*X)/g;
        y1=(x*Y)/g;

        printf("%lld %lld\n",x1,y1);
    }

}

10104 - Euclid Problem

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

Solution idea : Straight forward extended euclid.

Solution :

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


ll int X=-1,Y=-1;

ll int ext_gcd (ll int A,ll int B){
    ll int x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1; y2 = 0;
    x1 = 0; y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    X = x2;
    Y = y2;

    return r2;
}

int main()
{
    ll int a,b,e;
    while(scanf("%lld%lld",&a,&b)==2)
{
     e=ext_gcd(a,b);
     printf("%lld %lld %lld\n",X,Y,e);
}




}

11466 - Largest Prime Divisor

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

Solution Idea : Prime factorization. n can be negative.

Solution :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

bool status[10000055];

vector<ll int>prime;

ll int cnt=0;

void sieve()
{
    ll int n=10000000;
    ll int sq=sqrt(n);

    prime.push_back(2);

    for(int i=4; i<=n; i=i+2) status[i]=1;

    for(int i=3; i<=sq; i=i+2)
    {
        if(status[i]==0)
        {
            for(int j=i*i; j<=n; j=j+i)
            {
                status[j]=1;
            }
        }
    }
    status[1]=1;
    status[0]=1;

    for(int i=3; i<=n; i=i+2)
    {
        if(status[i]==0) prime.push_back(i);
    }
}

ll int nod(ll int n)
{

    ll int sq=sqrt(n);
    ll int mx=1;
    cnt=0;

    for(int i=0; i<prime.size() && prime[i]<=sq; i++)
    {

        if(n%prime[i]==0)
        {
            cnt++;
            while(n%prime[i]==0)
            {
                n=n/prime[i];

            }
            sq=sqrt(n);

            mx=max(mx,prime[i]);

        }
    }
    if(n!=1)
    {
        cnt++;
        mx=max(mx,n);

    }
    return mx;
}

int main()
{

    ll int n,s;
    sieve();

    while(scanf("%lld",&n) and n)
    {
        if(n<0) n=-1*n;
        s=nod(n);

        if( cnt<=1) printf("-1\n");

        else printf("%lld\n",s);
    }
}

583 - Prime Factors

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

Solution Idea : Prime factorization.

Solution :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

bool status[100000];

vector<ll int>prime;
vector<ll int>factor;

void sieve()
{
    ll int n=sqrt(2147483649);
    ll int sq=sqrt(n);

    prime.push_back(2);

    for(int i=4; i<=n; i=i+2) status[i]=1;

    for(int i=3; i<=sq; i=i+2)
    {
        if(status[i]==0)
        {
            for(int j=i*i; j<=n; j=j+i)
            {
                status[j]=1;
            }
        }
    }
    status[1]=1;
    status[0]=1;

    for(int i=3; i<=n; i=i+2)
    {
        if(status[i]==0) prime.push_back(i);
    }
}

void nod(ll int n,ll int sign)
{
    if(sign==1) n=-1*n;

    ll int sq=sqrt(n);


    for(int i=0; i<prime.size() && prime[i]<=sq; i++)
    {

        while(n%prime[i]==0)
        {
            n=n/prime[i];
            factor.push_back(prime[i]);
        }
        sq=sqrt(n);


    }
    if(n!=1)
    {
        factor.push_back(n);
    }

}

int main()
{
    ll int n,s,p;
    sieve();

    while(scanf("%lld",&n) and n)
    {
        s=0;
        if(n<0) s=1;

        nod(n,s);

        p=factor.size();
        printf("%lld = ",n);
        if(s==1) printf("-1 x ");
        printf("%lld",factor[0]);

        for(int i=1; i<p; i++)
        {
            printf(" x %lld",factor[i]);
        }
        printf("\n");
        factor.clear();
    }

}

11827 - Maximum GCD

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

Solution Idea : No idea needed to solve this problem!! But we will face problem while taking array elements..for this we have to use stringstream.

Solution :
#include<bits/stdc++.h>
#define ll long long

using namespace std;

ll int gcd(ll int p,ll int q)
{

    ll int gcd;

    ll int temp;
    while(q!=0){

        temp=q;
        q=p%q;
        p=temp;
    }

    gcd=p;
    return gcd;
}

ll int a[103];

int main()
{
    ll int n,m,mx=0,g=0,j=0,ans=0;
    string s;

    scanf("%lld",&n);
    getchar();

    while(n--)
    {
        getline(cin,s);
        stringstream ss(s);
        j=0;
        ans=0;
        while(ss>>a[j]) j++;

        for(int i=0;i<j;i++)
        {
            for(int k=i+1;k<j;k++)
            {
                g=gcd(a[i],a[k]);
                ans=max(ans,g);
            }

        }
        printf("%lld\n",ans);
    }

}

10892 - LCM Cardinality

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

Solution Idea :Easy lcm problem , where need to store all divisors of the n (no given) and then exploit bruteforce to find lcm of which pair of the divisors is equal to n (number given).

Solution :
#include<bits/stdc++.h>
#define ll long long
using namespace std;

vector<int>divisor;

void nod(ll int n)
{
    ll int sq=sqrt(n);
    ll int c=0;
     ll int m=0;

    for(ll int i=1;i<=sq;i++)
    {

        if(n%i==0)
        {
            c=n/i;
            divisor.push_back(i);
            if(c!=i) divisor.push_back(c);
        }
    }

}

ll int lcm(ll int p,ll int q)
{
     ll int c;
   c=p*q;
    ll int gcd,lcm;

    ll int temp;
    while(q!=0){

        temp=q;
        q=p%q;
        p=temp;
    }

    gcd=p;
    lcm=c/gcd;
    return lcm;

}

int main()
{

    ll int n,m,cnt=0,s;
    while(scanf("%lld",&n) and n)
    {
        nod(n);
        cnt=0;
         s=divisor.size();
        for(ll int i=0;i<s;i++)
        {
            for(ll int j=i;j<s;j++)
            {
                if(lcm(divisor[i],divisor[j])==n) cnt++;
            }
        }
        printf("%lld %lld\n",n,cnt);
        divisor.clear();
    }

}

10407 - Simple division

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

Tutorial : http://blog.forthright48.com/2015/08/uva-10407-simple-division.html

Solution :

#include<bits/stdc++.h>
#define ll long long

using namespace std;

vector<int>number;

ll int gcd(ll int p,ll int q)
{

    ll int gcd;

    ll int temp;
    while(q!=0){

        temp=q;
        q=p%q;
        p=temp;
    }

    gcd=p;
    return gcd;
}

int main()
{

    ll int n,g,m;
    while((scanf("%lld",&n)==1) and n)
    {


        while(1)
        {
            scanf("%lld",&m);
            if(m==0) break;
            number.push_back(abs(m-n));
            n=m;

        }
g=0;

       for(int i=0;i<number.size();i++)
        {
            g=gcd(g,number[i]);
        }

        printf("%lld\n",g);

        number.clear();
    }

}

Segmented Sieve Source Code

#include<bits/stdc++.h>

using namespace std;

bool status[1010000];

vector<int>prime;

void sieve()
{
    int n=1000100;
    int sq=sqrt(n);

    for(int i=4;i<=n;i=i+2) status[i]=true;

    for(int i=3;i<=sq;i=i+2)
    {
        if(status[i]==false)
        {
            for(int j=i*i;j<=n;j=j+(2*i)) status[j]=true;
        }
    }
    status[0]=true;
    status[1]=true;

    for(int i=2;i<=n;i++)
    {
        if(status[i]==false) prime.push_back(i);
    }
}

int arr[100010];

int sgmnt_sieve(int a,int b)
{
    memset(arr,0,sizeof(arr));

    if(a==1) a++;

    int sq=sqrt(b);

    for(int i=0;i<prime.size() and prime[i]<=sq;i++)
    {
        int p=prime[i];
       long long  int j=p*p;

        if(j<a) j=((a+p-1)/p)*p;

        for(;j<=b;j=j+p)
        {
            if(j<0) break;
            arr[j-a]=1;
        }

    }
    int cnt=0;

    for(int i=a;i<=b;i++)
    {
        if(arr[i-a]==0) cnt++;
    }

   return cnt;
}

int main()
{
    sieve();

int a,b,t,ca=1;
cin>>t;
    while(t--)
    {
           cin>>a>>b;
    cout<<"Case "<<ca<<": "<<sgmnt_sieve(a,b)<<endl;
ca++;
    }
}

10140 - Prime Distance

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

Solution Idea : Sieve then segmented sieve.

Solution :

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

bool status[101000];

vector<int>prime;

void sieve()
{
    int n=sqrt(2247483647);
    int sq=sqrt(n);

    for(int i=4;i<=n;i=i+2) status[i]=true;

    for(int i=3;i<=sq;i=i+2)
    {
        if(status[i]==false)
        {
            for(int j=i*i;j<=n;j=j+(2*i)) status[j]=true;
        }
    }
    status[0]=true;
    status[1]=true;

    prime.push_back(2);

    for(int i=3;i<=n;i=i+2)
    {
        if(status[i]==false) prime.push_back(i);
    }
}

int arr[1000003];

void sgmnt_sieve(ll int a,ll int b)
{
    memset(arr,0,sizeof(arr));

    if(a==1) a++;

   ll int sq=sqrt(b);

    for(ll int i=0;i<prime.size() and prime[i]<=sq;i++)
    {
        ll int p=prime[i];
       ll int j=p*p;

        if(j<a) j=((a+p-1)/p)*p;

        for(;j<=b;j=j+p)
        {
            if(j<0) break;
            arr[j-a]=1;
        }

    }
    ll int c1=0,c2=0,d1=0,d2=0,mn=1000000000,mx=-1,cnt=0,c11=0,c22=0,d11=0,d22=0;

    for(ll i=a;i<=b;i++)
    {
        if(arr[i-a]==0 and cnt%2==0) {
                c1=i;
                cnt++;
        }
        else if(arr[i-a]==0 and cnt%2!=0) {
                c2=i;
                cnt++;
                i--;
                if(c2-c1<mn)
                {
                    mn=c2-c1;
                    c11=c1;
                    c22=c2;
                }
        }
    }
    cnt=0;
      for(ll i=a;i<=b;i++)
    {
        if(arr[i-a]==0 and cnt%2==0) {
                d1=i;
                cnt++;
        }
        else if(arr[i-a]==0 and cnt%2!=0) {
                d2=i;
                cnt++;
                i--;
                if(d2-d1>mx)
                {
                    mx=d2-d1;
                    d11=d1;
                    d22=d2;
                }
        }
    }
    if(c22!=0) printf("%lld,%lld are closest, %lld,%lld are most distant.\n",c11,c22,d11,d22);
    else printf("There are no adjacent primes.\n");


}



int main()
{
    sieve();

ll int a,b;

    while(scanf("%lld%lld",&a,&b)==2)
    {

    sgmnt_sieve(a,b);

    }


}

Extended Euclid source code

Tutorial Link : http://blog.forthright48.com/2015/07/extended-euclidean-algorithm.html

Theorem : Let the solutions be X and Y , this algorithm gives the result as |X| + |Y | is the minimal. If there are several X and Y satisfying the minimal criteria, then the result follows the condition X ≤ Y.

Source Code :

#include<bits/stdc++.h>

using namespace std;


int X=-1,Y=-1;

int ext_gcd ( int A, int B){
    int x2, y2, x1, y1, x, y, r2, r1, q, r;
    x2 = 1; y2 = 0;
    x1 = 0; y1 = 1;
    for (r2 = A, r1 = B; r1 != 0; r2 = r1, r1 = r, x2 = x1, y2 = y1, x1 = x, y1 = y ) {
        q = r2 / r1;
        r = r2 % r1;
        x = x2 - (q * x1);
        y = y2 - (q * y1);
    }
    X = x2;
    Y = y2;

    return r2;
}

int main()
{
    int a,b;
    cin>>a>>b;

    int e=ext_gcd(a,b);

    cout<<"Gcd is :"<<e<<" and x="<<X<<" y="<<Y;
}

1007 - Mathematically Hard

Problem link : http://lightoj.com/volume_showproblem.php?problem=1007

Solution Idea : This problem teaches you the use of unsigned long long data type.The problem is the modified application Euler Phy's algorithm .

Solution :

#include<bits/stdc++.h>

using namespace std;

bool status[5000005];

vector<int>prime;

void sieve()
{
    int n=5000000;
    int sq=sqrt(n);

    for(int i=4; i<=n; i=i+2) status[i]=true;

    for(int i=3; i<=sq; i=i+2)
    {
        if(status[i]==false)
        {

            for(int j=i*i; j<=n; j=j+i) status[j]=true;
        }
    }
    status[1]=1;
    status[0]=1;

    prime.push_back(2);

    for(int i=3; i<=n; i=i+2)
    {
        if(status[i]==false) prime.push_back(i);
    }
}


unsigned long long  phi[5000505];

int main()
{

    sieve();

    for (int i = 1; i <= 5000000; i++)
    {
        phi[i] = i;
    }

    int w,tr;
    for (int p = 0; p < prime.size(); p++)
    {
        w=prime[p];
        for (int k = w; k <= 5000000; k =k+w)
        {
            phi[k] -= phi[k] / w;


        }

    }
    phi[1]=0;
    phi[0]=0;

    for(int i=1; i<=5000000; i++ )
    {
        phi[i]=phi[i]*phi[i];
        phi[i]=phi[i]+phi[i-1];
    }

    long long int t,a,b;

    scanf("%lld",&t);
    unsigned long long temp;

    for(long long int ca=1; ca<=t; ca++)
    {
        scanf("%lld%lld",&a,&b);
        temp=phi[b]-phi[a-1];
        printf("Case %lld: %llu\n",ca,phi[b]-phi[a-1]);
    }
}

EulerPhi source code

Theorem 1: If m and n are coprime, then ϕ(m×n)=ϕ(m)×ϕ(n)


Theorem 2: In an arithmetic progression with difference of m, if we take n terms and find their modulo by n, and if n and m are coprimes, then we will get the numbers from 0 to n−1 in some order.

Theorem 3: If a number x is coprime to y, then (x%y) will also be coprime to y.

#include<bits/stdc++.h>

using namespace std;

bool status[11000010];

vector<int>prime;

void sieve()
{
    int n=10000010;
    int sq=sqrt(n);

    for(int i=4; i<=n; i=i+2) status[i]=true;

    for(int i=3; i<=sq; i=i+2)
    {
        if(status[i]==false)
        {

            for(int j=i*i; j<=n; j=j+i) status[j]=true;
        }
    }
    status[1]=1;
    status[0]=1;

    prime.push_back(2);

    for(int i=3; i<=n; i=i+2)
    {
        if(status[i]==false) prime.push_back(i);
    }
}

long long int EulerPhi(long long int n)
{
    long long  int res=n;
    long long int sq=sqrt(n);

    for(long long int i=0; i<prime.size() and prime[i]<=sq; i++)
    {
        if(n%prime[i]==0)
        {
            while(n%prime[i]==0)
            {
                n=n/prime[i];
            }
            sq=sqrt(n);
            res=res/prime[i];
            res=res*(prime[i]-1);
        }

    }
    if(n!=1)
    {
        res=res/n;
        res=res*(n-1);
    }
    return res;
}

int main()
{
    sieve();
    long long int n;

    while(cin>>n)
    {
        cout<<EulerPhi(n)<<endl;
    }
}