UVA 11770 - Lighting Away

#include<bits/stdc++.h>
using namespace std;
#define mx 50000*3
long vis[mx];
vector<long>vec[mx];
void dfs(long u)
{
    vis[u]=1;
    for(long i1=0;i1<vec[u].size();i1++)
    {
        if(vis[vec[u][i1]]==0)
        dfs(vec[u][i1]);
    }
}
int main()
{
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        memset(vis,0,sizeof(vis));
        long node,edge,i,a,b,cnt=0;
        cin>>node>>edge;
        for(i=1;i<=edge;i++)
        {
            cin>>a>>b;
            vec[a].push_back(b);
        }
        vector<long>tostore;
        for(i=1;i<=node;i++)
        {
            if(vis[i]==0)
            {
                dfs(i);
                tostore.push_back(i);
            }
        }
        memset(vis,0,sizeof(vis));
        for(i=tostore.size()-1;i>=0;i--)
        {
            if(vis[tostore[i]]==0)
            {
                dfs(tostore[i]);
                cnt++;
            }
        }
        printf("Case %ld: %ld\n",cs++,cnt);
        for(i=0;i<=node;i++)
        {
            vec[i].clear();
        }
        tostore.clear();
    }
}

UVA 11876 - N + NOD (N)

#include<bits/stdc++.h>
using namespace std;
long divisor[1000010],ar[1000010]={0},tot;
void divisors()
{
    long i,j;
    for(i=1;i<=1000000;i++)
    {
        for(j=i;j<=1000000;j+=i)
            divisor[j]++;
    }
}
long binarysearch(long start,long ennd,long ele)
{
    while(start<ennd)
    {
        long mid=(start+ennd)/2;
        if(ele==ar[mid])
            return mid;
        else if(ele==ar[start])
            return start;
        else if(ele==ar[ennd])
            return ennd;
        else if(ele>ar[mid])
        {
            start=mid+1;
        }
        else if(ele<ar[mid])
        {
            ennd=mid-1;
        }
    }
    return start;
}
void nod()
{
    memset(ar,0,sizeof(ar));
    ar[0]=1;
    ar[1]=2;
    ar[2]=4;
    long i;
    for(i=3;ar[i-1]<1000010;i++)
    {
        ar[i]=ar[i-1]+divisor[ar[i-1]];
        tot=i;
    }
}
int main()
{
    divisors();
    nod();
    long ts,cs=1;
    cin>>ts;
    while(ts--)
    {
        long fst,scnd,a,b;
        cin>>a>>b;
        fst=binarysearch(0,tot,a);
        scnd=binarysearch(0,tot,b);
        if(ar[fst]<a)
            fst++;
        if(ar[scnd]>b)
            scnd--;
        printf("Case %ld: %ld\n",cs++,scnd-fst+1);
    }
}

UVA 10290 - {Sum+=i++} to Reach N

#include <bits/stdc++.h>
using namespace std;
#define sze 10000100
bool vis[sze];
vector<long long>ar;
void sieve()
{
    long long i,j;
    for(i=3; i<sze; i+=2)
    {
        if(vis[i]==0)
        {
            ar.push_back(i);
            for(j=2*i; j<sze; j+=(i))
            {
                vis[j]=1;
            }
        }
    }
}
long long check(long long a)
{
    long long ans=1,i1,xx=sqrt(a);
    while(a%2==0)
    {
        a/=2;
    }
    for(i1=0; ar[i1]<=xx&&i1<ar.size(); i1++)
    {
        if(a%ar[i1]==0)
        {
            long long cnt=0;
            while(a%ar[i1]==0)
            {
                a/=ar[i1];
                cnt++;
            }
            ans*=(cnt+1);
        }
        xx=sqrt(a);
    }
    if(a>1)
    {
        ans*=2;
    }
    return ans-1;
}
int main()
{
    sieve();
    long long n;
    while(cin>>n)
    {
        if(n>=3)
        printf("%lld\n",check(n)+1);
        else
            printf("1\n");
    }
    return 0;
}

UVA 10664 - Luggage

#include<bits/stdc++.h>
using namespace std;
long ar[110]= {0},tot=0,sum=0,dp[50][3000];
#define sf(a) scanf("%ld",&a)
long call(long i,long wt)
{
    if(i>tot)
        return 0;
    if(wt==sum/2)
        return 1;
    if(dp[i][wt]!=-1)
        return dp[i][wt];
    long ans=0;
    ans=ans|call(i+1,wt+ar[i]);
    ans=ans|call(i+1,wt);
    return dp[i][wt]=ans;
}
int main()
{
    long ts,num;
    string line;
    sf(ts);
    getchar();
    while(ts--)
    {
        getline(cin,line);
        stringstream ss;
        ss<<line;
        int cnt=0;
        sum=0;
        memset(dp,-1,sizeof(dp));
        while(ss>>num)
        {
            ar[cnt++]=num;
            sum+=num;
        }
        tot=cnt-1;

        if(sum%2==0)
        {
            // cout<<call(0,0);
            if(call(0,0))
                printf("YES\n");
            else
                printf("NO\n");
        }
        else
            printf("NO\n");
    }
    return 0;
}

UVa 10692 - Huge Mods

// Theory: a ^ ( b % phi[m]) + phi[m]
// suppose, m=53, n=3, and a1=2, a2=3 and a3=2; then: m=53, m1=phi[m]=52, m2=phi[m1]=24;
// we know: 2 ^ 3 ^ 2 % m ; that means it will be 2 ^ 3 ^ 2 ^ 1
// We have to start from the last, so: ans1 = (2 ^ 1 % m2) + m2=26; which is mod(2 , ans, m2), ans=1 here;
// ans2 = (( 3 ^ ans1) % m1) + m1 = 61; which is mod(3 , ans, m1), ans=ans1;
// main_ans = (2 ^ ans2) % m=35; which is mod(2 , ans, m), ans = ans2;

#include<bits/stdc++.h>
using namespace std;
#define sze 10010
char s[sze];
long phi[sze],vis[sze],i1,j;
void euler_phi()
{
    for(i1=1; i1<=sze; i1++)
        phi[i1]=i1;
    for(i1=2; i1<=sze; i1++)
    {
        if(vis[i1]==0)
        {
            for(j=i1; j<=sze; j+=i1)
            {
                phi[j]=(phi[j]/i1)*(i1-1);
                vis[j]=1;
            }
        }
    }
}
long bigmod(long base,long power,long mod)
{
    if(power==0)
        return 1;
    else if(power%2==0)
    {
        long xx=bigmod(base,power/2,mod);
        return ((xx%mod)*(xx%mod))%mod;
    }
    else
    {
        return ((base%mod)*(bigmod(base,power-1,mod)%mod))%mod;
    }
}
main()
{
    euler_phi();
    long cs=1;
    while(cin>>s)
    {
        if(s[0]=='#')
            break;
        else
        {
            long x=atoi(s),ar[10010]={0},ar1[10010]={0},n,x2,i;
            x2=x;
            cin>>n;
            for(i=1;i<=n;i++)
            {
                cin>>ar[i];
            }
            ar1[1]=x2;
            for(i=2;i<=n;i++)
            {
                x2=phi[x2];
                ar1[i]=x2;
            }
            long ans=1;
            for(i=n;i>=2;i--)
            {
                ans=bigmod(ar[i],ans,ar1[i]);
                ans+=ar1[i];
            }
            ans=bigmod(ar[1],ans,ar1[1]);
            printf("Case #%ld: %ld\n",cs++,ans);
        }
    }
}

UVA 147 - Dollars

#include<bits/stdc++.h>
using namespace std;
long long coin[]= {10000,5000,2000,1000,500,200,100,50,20,10,5};
long long  dp[12][30005];
long long  c;
long long  func(long long  i,long long  w)
{
    if(i>=11)
    {
        if(w==0)
            return 1;
        else
            return 0;
    }
    if(dp[i][w]!=-1)
        return dp[i][w];
    long long  p1=0,p2=0;
    if(w-coin[i]>=0)
        p1=func(i,w-coin[i]);
    p2=func(i+1,w);
    return dp[i][w]=p1+p2;

}
int main()
{
    long long  x,y;
    char ch;
    memset(dp,-1,sizeof(dp));
    while(cin>>x>>ch>>y)
    {
        long long n,n1;
        if(x==0&&y==0)
            break;
        else
        {
            n=x*100+y;
            {
                n1=func(0,n);
                printf("%3lld.%.2lld%17lld\n",x,y,n1);
            }
        }

    }
    return 0;

}

Upper bound by using binary search

#include<bits/stdc++.h>
using namespace std;
#define fr(i,x) for(i=0;i<x;i++)
int binaryupper(int a[],int m,int l,int u)
{
    int mid,c=0;
    if(l<=u)
    {
        mid=(l+u)/2;
        if(m==a[mid])
        {
            c=m;
            return binaryupper(a,m,mid+1,u);
        }
        else if(m<a[mid])
        {
            return binaryupper(a,m,l,mid-1);
        }
        else
        {
            return binaryupper(a,m,mid+1,u);
        }
    }
    else
        return u;
}
int main()
{
    int n;
    while(cin>>n)
    {
        int ar[100010]= {0},i,a;
        fr(i,n)
        {
            cin>>ar[i];
        }
        cin>>a;
        cout<<binaryupper(ar,a,0,n-1)<<endl;
    }
}