BIGMOD if base power and mod<=10^18

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

template <typename T>
T mmul(T a, T b, T m)
{
    a %= m;
    T result = 0;
    while (b)
    {
        if (b % 2) result = (result + a) % m;
        a = (a + a) % m;
        b /= 2;
    }
    return result;
}

template <typename T>
T mpow(T a, T b, T m)
{
    a %= m;
    T result = 1;
    while (b)
    {
        if (b % 2) result = mmul(result, a, m);
        a = mmul(a, a, m);
        b /= 2;
    }
    return result;
}


int main()
{
    unsigned long long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        unsigned long long a,b1,c;
        cin>>a>>b1>>c;
        printf("Case %llu: ",cs++);
        cout<<mpow(a,b1,c)<<endl;
    }
}

Maxmum path by using dijkstra ( node 0 to node n-1 )

//input
/*4
0 1 4
0 2 2
2 3 3
output=5=(2+3)*/

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

//#define maximum 10000
//#define INF 1000000
vector <int> edges[1000];
vector <int> cost[1000];
int N, E;

struct data {
    int city, dist;
    bool operator < ( const data& p) const {
        return dist < p.dist;
    }
};

int dijsktra(int source, int destination)
{
    priority_queue <data> q;
    vector <int> distance;

    for(int i = 0; i <= N; i++)
        distance.push_back(-1);

    int maxi = -1;

    data u, v;
    u.city = source, u.dist = 0;
    q.push(u);
    distance[source] = 0;
    while(!q.empty()) {
        u = q.top();
        int ucost = distance[u.city];
        q.pop();
        //if(u.city == destination)
           // return distance[u.city];
        int sz = edges[u.city].size();
        for(int i = 0; i < sz; i++) {
            v.city = edges[u.city][i], v.dist = cost[u.city][i] + ucost;
            if(distance[v.city] == -1) {
                distance[v.city] = v.dist;
                q.push(v);
                maxi = max(maxi, v.dist);
            }
        }
    }
    return maxi;
}

int main()
{
    scanf("%d", &N);

    for(int i = 1; i < N; i++) {
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        edges[x].push_back(y);
        edges[y].push_back(x);
        cost[x].push_back(c);
        cost[y].push_back(c);
    }

    //int source, destination;
    //scanf("%d %d", &source, &destination);
    int maximum_cost = dijsktra(0, N-1);

    cout << maximum_cost << endl;
    return 0;
}

UVA 11221 - Magic square palindromes.

#include <bits/stdc++.h>
using namespace std;
main()
{
    long ts,cs=1;
    cin>>ts;
    getchar();
    while(ts--)
    {
        string s,s1,s2;
        long l,i,flag=0,k,ss;
        getline(cin,s);
        l=s.size();
        for(i=0;i<l;i++)
        {
            if(isalpha(s[i]))
            {
                s1+=s[i];
            }
        }
        s2=s1;
        ss=s2.size();
        k=sqrt(ss);
        reverse(s1.begin(),s1.end());
        if(s1==s2)
        {
            if(k*k==ss)
            flag=1;
        }
        if(flag==0)
        {
            printf("Case #%ld:\nNo magic :(\n",cs++);
        }
        else
        {
            printf("Case #%ld:\n%ld\n",cs++,k);
        }
    }
}

UVA 10656 - Maximum Sum (II)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long n;
    while(cin>>n)
    {
        if(n==0)
            break;
        long long i,j,k=0,a,ar[2000],sum=0;
        for(i=0; i<n; i++)
        {
            cin>>a;
            if(a>0)
            {
                ar[k++]=a;
            }
        }
        if(k==0)
            printf("0\n");
        else
        {
            for(i=0; i<k; i++)
            {
                if(i==0)
                    printf("%ld",ar[i]);
                else
                    printf(" %ld",ar[i]);
            }
            cout<<endl;
        }
    }
    return 0;
}

 

secuence of palindrome number (N<=100)

for n=12 output is 1,2,3,4,5,6,7,8,9,11,22,33

#include <bits/stdc++.h>
using namespace std;
main()
{
    long n,i,k,k1;
    while(cin>>n)
    {
        for(i=1; i<=n; i++)
        {
            if(i<=9)
                cout<<i<<" ";
            else if(i<=18)
            {
                k=i-9;
                cout<<k*11<<" ";
            }
            else
            {
                k=(i-19)%10;
                k1=(i-k)/10;
                while(k1>=10)
                {
                    k1/=10;
                }
                printf("%ld%ld%ld ",k1,k,k1);
            }
        }
    }
}

UVA 11137 - Ingenuous Cubrency

#include <bits/stdc++.h>
using namespace std;
//long long coin[]={1,8,27,64.125,216,343,512,729,1000,1331,1728,2197,2744,3375,4096,4913,5832,6859,8000,9261};
long long coin[]= {9261,8000,6859,5832,4913,4096,3375,2744,2197,1728,1331,1000,729,512,343,216,125,64,27,8,1};
long long ar[10010],mx=10010;
void chk()
{
    long long i,j;
    ar[0]=1;
    for(i=0; i<21; i++)
    {
        for(j=coin[i]; j<mx; j++)
        {
            ar[j]+=ar[j-coin[i]];
        }
    }
}
main()
{
    chk();
    long long n;
    while(scanf("%lld",&n)!=EOF)
    {
        printf("%lld\n",ar[n]);
    }

}

UVA 674 - Coin Change

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
long long coin[]={1,5,10,25,50};
long long dp[6][30005],n,ar[30005];
long coinchange(long i,long make)
{
  if(i==5)
  {
      if(make==0)
        return 1;
      else
        return 0;
  }
  long long ret1=0,ret2=0;
  if(dp[i][make]!=-1) return dp[i][make];
  if(make-coin[i]>=0)
  {
      ret1=coinchange(i,make-coin[i]);
  }
  ret2=coinchange(i+1,make);
  return dp[i][make]=ret1+ret2;
}
main()
{
    memset(dp,-1,sizeof(dp));
    for(long long i1=0;i1<=30000;i1++)
    {
        ar[i1]=coinchange(0,i1);
    }
    while(cin>>n)
    {
        cout<<ar[n]<<endl;
    }
}

 

Longest Increasing Subsecuence ( LIS ) Length and path

for this topic : best video link
https://www.youtube.com/watch?v=1RpMc3fv0y4

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const long  maxn = 100000;
long x[maxn],i,n,length=0,increasingSub[maxn],parent[maxn],LIS[maxn],j;
long lis(long x[])
{
    for(i=0; i<n; i++)
    {
        long low=1;
        long  high=length;
        while(low <= high)
        {
            long mid =(low + high)/2;
            if(x[increasingSub[mid]] < x[i])
                low = mid + 1;
            else
                high = mid - 1;
        }
        long pos = low;
        parent[i] = increasingSub[pos-1];
        increasingSub[pos] =  i;
        if(pos > length)
            length=pos;
    }
    long  k=increasingSub[length];
    for(j=length-1; j>=0; j--)
    {
        LIS[j] =  x[k];
        k = parent[k];
    }
    printf("LIS Length = ");
     cout<<length<<endl;
     printf("LIS Path = ");
    for(i=0; i<length; i++)
    {
        cout<<LIS[i]<<" ";
    }

}
main()
{
    printf("Enter the size of array = ");
    cin>>n;
    for(i=0; i<n; i++)
    {
        cin>>x[i];
    }
    long long ll=lis(x);

}

UVA 481 - What Goes Up

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const long  maxn = 1000010;
long x[maxn],i,n,length=0,increasingSub[maxn],parent[maxn],LIS[maxn],j;
long lis(long x[])
{
    for(i=0; i<n; i++)
    {
        long low=1;
        long  high=length;
        while(low <= high)
        {
            long mid =(low + high)/2;
            if(x[increasingSub[mid]] < x[i])
                low = mid + 1;
            else
                high = mid - 1;
        }
        long pos = low;
        parent[i] = increasingSub[pos-1];
        increasingSub[pos] =  i;
        if(pos > length)
            length=pos;
    }
    long  k=increasingSub[length];
    for(j=length-1; j>=0; j--)
    {
        LIS[j] =  x[k];
        k = parent[k];
    }
    printf("%ld\n-\n",length);
    for(i=0; i<length; i++)
    {
        printf("%ld\n",LIS[i]);
    }

}
main()
{
    n=0;
    long i1,a;
    for(i1=0;;i1++)
    {
        if(scanf("%ld",&a)!=1)
        {
            break;
        }
        x[n++]=a;
    }
    long long ll=lis(x);
}

UVA 12032 - The Monkey and the Oiled Bamboo

#include <bits/stdc++.h>
using namespace std;
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        long long ar[100010]={0},n,diff,i,ans=0;
        cin>>n;
        ar[0]=0;
        for(i=1;i<=n;i++)
        {
            cin>>ar[i];
        }
        long long  mx=0;
        for(i=1;i<=n;i++)
        {
            diff=ar[i]-ar[i-1];
            if(diff>mx)
            {
                mx=diff;
            }
        }
        ans=mx;
        for(i=1;i<=n;i++)
        {
            diff=ar[i]-ar[i-1];
            if(diff==mx)
            {
                mx--;
            }
            else if(diff>mx)
            {
                ans++;
                break;
            }
        }
        printf("Case %ld: %lld\n",cs++,ans);
    }
}

UVA 10130 - SuperSale

#include<bits/stdc++.h>
using namespace std;
#define SIZE 1002
int i,n,dp[SIZE][32],wt[SIZE],num[SIZE],qry,chk;
int knap(int i1,int weight)
{
    if(i1==n)
        return 0;
    if(dp[i1][weight]!=-1) return dp[i1][weight];
      dp[i1][weight]=knap(i1+1, weight);
      //int profit1=dp[i1][weight];
    if(weight>=wt[i1])
        dp[i1][weight]=max(dp[i1][weight], num[i1]+knap(i1+1, weight-wt[i1]));
return dp[i1][weight];
}
main()
{
    int ts;
    scanf("%d",&ts);
    while(ts--)
    {
        int sum=0;
        scanf("%d",&n);
        for(i=0; i<n; i++)
        {
            scanf("%d%d",&num[i],&wt[i]);
        }
        memset(dp,-1,sizeof(dp));
        scanf("%d",&qry);
        while(qry--)
        {
           scanf("%d",&chk);
            sum+=knap(0, chk);
        }
         printf("%d\n",sum);
    }
}

UVA 11057 - Exact Sum

#include<bits/stdc++.h>
using namespace std;
long long ar[1000005];
main()
{
    long long n;
    while(scanf("%lld",&n)!=EOF)
    {
        long long diff,fst,scnd,flag=0,i,j,ans=0,a;
        for(i=0; i<n; i++)
        {
            scanf("%lld",&ar[i]);
        }
        scanf("%lld",&a);
        sort(ar,ar+n);
        for(i=0; i<n; i++)
        {
            for(j=i+1; j<n; j++)
            {
                if((ar[j]+ar[i])==a)
                {

                    diff=ar[j]-ar[i];
                    if(flag==0||diff<ans)
                    {
                        ans=diff;
                        fst=ar[i];
                        scnd=ar[j];
                        flag=1;
                    }
                }
            }
        }
        printf("Peter should buy books whose prices are %lld and %lld.\n\n",fst,scnd);
    }
}

UVA 10212 The Last Non-zero Digit.

 #include<bits/stdc++.h>
using namespace std;
int main()
{
    long long a,b;
    while(cin>>a>>b)
    {
        long long ans=1,k,i;
        k=(a-b)+1;
        if(b==0)
            ans=1;
        else
        {
        for(i=a;i>=k;i--)
        {
            ans*=i;
            while(ans%10==0)
            {
                ans/=10;
            }
            ans%=1000000000;
        }
        }
        cout<<ans%10<<endl;
    }
    return 0;
}

UVA 10176 Ocean Deep! Make it shallow!!

 #include<cmath>
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
int main()
{
    char ch;
    int i,s,R=131071;
    while(1)
    {
        string p="";
        for(i=0;;i++)
        {
            if(scanf(" %c",&ch)==EOF)
                return 0;
            else if( ch =='#')
                break;
            else
                p+=ch;
        }
        s=0;
        for (int i=0;i<p.length(); i++)
        {
            s *= 2;
            s += p[i]-'0';
            s %= R;
        }
        if(!s)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}

UVA 10013 - Super long sums

#include<bits/stdc++.h>
using namespace std;
#define siz 1000009
long long ar[siz],ar1[siz],ar2[siz];
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        if(cs>1)
            cout<<endl;
        cs++;
        long i,a,k,k1,sum=0,carry=0,k2=0;
        cin>>a;
        for(i=0;i<a;i++)
        {
            cin>>ar[i]>>ar1[i];
        }
        for(i=a-1;i>=0;i--)
        {
            k=ar[i];
            k1=ar1[i];
            sum=k+k1+carry;
            if(sum>9)
                carry=1;
            else
                carry=0;
            ar2[k2++]=(sum%10);
        }
        if(carry==1)
        {
            ar2[k2++]=1;
        }
        for(i=k2-1;i>=0;i--)
            cout<<ar2[i];
            cout<<endl;
    }
}

UVA 1266 - Magic Square

#include<bits/stdc++.h>
using namespace std;
main()
{
    long n,cs=1;
    while(cin>>n)
    {
        if(cs!=1)
        printf("\n");
        long j,i,k=1,k1=n/2+1,a=1,ar[20][20]={0},cnt=1,cnt1=0,kk,sum=0;
        kk=n;
        while(kk!=0)
        {
            kk/=10;
            cnt1++;
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                ar[k][k1]=cnt++;
                k--;
                k1++;
                if(k==0)
                {
                    k=n;
                }
                if(k1==n+1)
                    k1=1;
            }
            k+=2;
            if(k>n)
                k=k-n;
            k1--;
        }
        ar[2][n]=ar[1][n]+1;
        for(i=1;i<=n;i++)
        {
            sum+=ar[1][i];
        }
        printf("n=%ld, sum=%ld\n",n,sum);
        if(n>=1&&n<=3)
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                printf(" %ld",ar[i][j]);
            }
            cout<<endl;
        }
        else if(n>=4&&n<=9)
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                printf(" %2ld",ar[i][j]);
            }
            cout<<endl;
        }
        else
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                printf(" %3ld",ar[i][j]);
            }
            cout<<endl;
        }
        cs++;
    }
}

UVA 11254 Consecutive Integers

#include<bits/stdc++.h>
using namespace std;
main()
{
    long long n;
    while(cin>>n)
    {
        if(n==-1)
            break;
        long long k,i,s,a;
        k=sqrt(2*n);
        for(i=k;i>=1;i--)
        {
            s=(pow(i,2)+.00000000001);
            s=(2*n)+i-s;
            a=s/(2*i);
            if(s%(2*i)==0)
            {
                break;
            }
        }
        printf("%lld = %lld + ... + %lld\n",n,a,(a+i-1));
    }
}

UVA 11804 - Argentina

#include<bits/stdc++.h>
using namespace std;
struct A
{
    long a1,b1;
    string s1;
    bool operator < (const A &b) const
    {
        if(a1==b.a1)
        {
            if(b1==b.b1)  return s1<b.s1;
            else
                return b1<b.b1;
        }
        else
            return a1>b.a1;
    }
};
main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        long i,a,b;
        string s;
        vector<A>vb;
        vector<string>vb1,vb2;
        set<string>ss1,ss2;
        A stk;
        for(i=0; i<10; i++)
        {
            cin>>s>>a>>b;
            stk.s1=s;
            stk.a1=a;
            stk.b1=b;
            vb.push_back(stk);
        }
        sort(vb.begin(),vb.end());
        for(i=0;i<5;i++)
        {
            vb1.push_back(vb[i].s1);
        }
        for(i=5;i<10;i++)
        {
            vb2.push_back(vb[i].s1);
        }
        sort(vb1.begin(),vb1.end());
        sort(vb2.begin(),vb2.end());
        printf("Case %ld:\n",cs++);
        cout<<"(";
        for(i=0;i<vb1.size()-1;i++)
        {
            cout<<vb1[i]<<", ";
        }
        cout<<vb1[4]<<")"<<endl;
        cout<<"(";
        for(i=0;i<vb2.size()-1;i++)
        {
            cout<<vb2[i]<<", ";
        }
        cout<<vb2[4]<<")"<<endl;
    }
}

UVA 11287 - Pseudoprime Numbers

#include<bits/stdc++.h>
using namespace std;
long long isPrime(long long  x)
{
    long long i;
    for(i = 2; i*i <= x; i++)
        if(x%i == 0)
            return 0;
    return 1;
}
long long bigmod(long long bb,long long pp,long long m)
{
    if(bb==0) return 0;
    long long x,power;
    x=1;
    power=bb%m;
    while(pp)
    {
        if(pp%2==1)
            x=(x*power)%m;
        power=(power*power)%m;
        pp=pp/2;
    }
    return x;
}
main()
{
    long long a,b;
    while(cin>>a>>b)
    {
        if(a==0&&b==0)
            break;
        if(isPrime(a))
        {
            printf("no\n");
        }
        else
        {
            long long k=bigmod(b,a,a);
            if(k==b)
            {
                printf("yes\n");
            }
            else
                printf("no\n");
        }
    }
}