UVA 11690 - Money Matters

# include<sstream>
# include<bits/stdc++.h>
using namespace std;
long par[50010];
long find(long xx)
{
    if(par[xx]==xx)
        return xx;
    return par[xx]=find(par[xx]);
}
void unionkorlam(long a,long b)
{
    if(find(a)!=find(b))
    {
        par[find(b)]=find(a);
    }
}
main()
{
    long ts;
    cin>>ts;
    while(ts--)
    {
        long n,m,i,x,y,tot[50010]={0},flag=0,ar[50010]={0},yy;
        cin>>n>>m;
        for(i=0;i<n;i++)
        {
            cin>>ar[i];
            par[i]=i;
        }
        for(i=0;i<m;i++)
        {
            cin>>x>>y;
            unionkorlam(x,y);
        }
        for(i=0;i<n;i++)
        {
            yy=find(i);
            tot[yy]+=ar[i];
        }
        for(i=0;i<n;i++)
        {
            if(tot[i]<0)
            {
                flag=1;
            }
        }
        if(flag==1)
        {
            cout<<"IMPOSSIBLE"<<endl;
        }
        else
            cout<<"POSSIBLE"<<endl;
    }
}

UVA 11094 - Continents

#include <bits/stdc++.h>
using namespace std;
#define mxx 25;
//string s[25];
char s[25][25],x;
int vis[25][25],n,m,cnt;
int floodfill(int i1,int j1)
{
    int cnt=1;
    if(j1==m)
        j1=0;
    else if(j1==-1)
        j1=m-1;
    if(i1<0||i1>=n||j1<0||j1>=m)
         return 0;
    if(vis[i1][j1])
         return 0;
    if(s[i1][j1] != x)
        return 0;
    vis[i1][j1]=1;
    cnt+=floodfill(i1,j1+1);
    cnt+=floodfill(i1-1,j1);
    cnt+=floodfill(i1,j1-1);
    cnt+=floodfill(i1+1,j1);
    return cnt;
}
int main()
{
    while(cin>>n>>m)
    {
        int i,a,b,j,ans=0,mx=0;
        for(i=0;i<n;i++)
        {
            cin>>s[i];
        }
        cin>>a>>b;
        x=s[a][b];
        floodfill(a,b);
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
                {
                    if(s[i][j]==x)
                    {
                        cnt=0;
                        ans=floodfill(i,j);
                        mx=max(mx,ans);
                    }
                }
        }
        cout<<mx<<endl;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            vis[i][j]=0;
        }
    }
}

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