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;

}