Light OJ 1012 (Guilty Prince)

#include<bits/stdc++.h>
using namespace std;
int x[4]={-1,0,1,0};
int y[4]={0,-1,0,1};
int graph[100][100];
int visited[100][100];
int level[100][100];
int main()
{
    int test,k;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        for(int i=0;i<100;i++)
        {
            for(int j=0;j<100;j++)
            {
                graph[i][j]=0;
                visited[i][j]=0;
                level[i][j]=0;
            }
        }
        int r,c,stx,sty;
        cin>>r>>c;
        for(int i=0;i<c;i++)
        {
            string s;
            cin>>s;
            for(int j=0;j<r;j++)
            {
                if(s[j]=='.')
                    graph[i][j]=0;
                if(s[j]=='#')
                    graph[i][j]=1;
                if(s[j]=='@')
                {
                    stx=i;
                    sty=j;
                    graph[i][j]=0;
                }
            }

        }
        queue<int>q;
        q.push(stx);
        q.push(sty);
        visited[stx][sty]=1;
        level[stx][sty]=0;
        int cnt=0;
        while(!q.empty())
        {
            int f1=q.front();
            q.pop();
            int f2=q.front();
            q.pop();
            for(int i=0;i<4;i++)
            {
                int v1=f1+x[i];
                int v2=f2+y[i];
                if(visited[v1][v2]!=1&&graph[v1][v2]==0&&v1>=0&&v1<c&&v2>=0&&v2<r)
                {
                    cnt++;
                    //cout<<cnt<<endl;
                    visited[v1][v2]=1;
                    q.push(v1);
                    q.push(v2);
                }
            }
        }
        cout<<"Case "<<k<<": "<<cnt+1<<endl;
    }
    return 0;
}

UVa 439 - Knight Moves

#include<bits/stdc++.h>
using namespace std;
int graph[50][50];
int visited[50][50];
int level[50][50];
int x[8]={-2,-2,2,2,1,1,-1,-1};
int y[8]={-1,1,-1,1,-2,2,-2,2};
int main()
{
    string s1,s2;
    while(cin>>s1>>s2)
    {
        memset(graph,0,sizeof(graph));
        memset(visited,0,sizeof(visited));
        memset(level,0,sizeof(level));
        queue<int>q;
        int stx,sty,enx,eny;
        stx=s1[0]-96;
        sty=s1[1]-48;
        enx=s2[0]-96;
        eny=s2[1]-48;
        visited[stx][sty]=true;
        level[stx][sty]=0;
        q.push(stx);
        q.push(sty);
        int ans;
        while(!q.empty())
        {
            int f1,f2;
            f1=q.front();
            q.pop();
            f2=q.front();
            q.pop();
            for(int in=0;in<8;in++)
            {
                int v1,v2;
                v1=f1+x[in];
                v2=f2+y[in];
                if(!visited[v1][v2]&&!level[v1][v2])
                {
                    if(v1>=1&&v1<=8&&v2>=1&&v2<=8)
                    {
                        level[v1][v2]=level[f1][f2]+1;
                        if(v1==enx&&v2==eny)
                            ans=level[v1][v2];
                        q.push(v1);
                        q.push(v2);
                        visited[v1][v2]=true;
                    }
                }
            }
        }
        cout<<"To get from "<<s1<<" to "<<s2<<" takes ";
        if(stx==enx&&sty==eny)
            cout<<0;
        else
            cout<<ans;
        cout<<" knight moves.\n";
    }
    return 0;
}

UVa 10653 - Bombs! NO they are Mines!!

#include<bits/stdc++.h>
using namespace std;
int graph[1009][1009];
int visited[1009][1009];
int level[1009][1009];
int x[4]={-1,0,1,0};
int y[4]={0,-1,0,1};
int main()
{
    while(1)
    {
        int r,c;
        cin>>r>>c;
        if(r==0&&c==0)
            break;
        int row_num;
        cin>>row_num;
        memset(graph,0,sizeof(graph));
        int row,i,j,k;
        for(i=0;i<row_num;i++)
        {
            cin>>row>>k;
            for(j=0;j<k;j++)
            {
                int col;
                cin>>col;
                graph[row][col]=1;
                //cout<<"ROW:"<<row<<" COL:"<<col<<endl;
            }
        }
        memset(visited,0,sizeof(visited));
        memset(level,0,sizeof(level));
        queue<int>q;
        int stx,sty,enx,eny;
        cin>>stx>>sty;
        cin>>enx>>eny;
        visited[stx][sty]=true;
        level[stx][sty]=0;
        q.push(stx);
        q.push(sty);
        int ans;
        while(!q.empty())
        {
            int f1,f2;
            f1=q.front();
            q.pop();
            f2=q.front();
            q.pop();
            for(int in=0;in<4;in++)
            {
                int v1,v2;
                v1=f1+x[in];
                v2=f2+y[in];
                //cout<<111111111111<<endl;
                if(!visited[v1][v2]&&!level[v1][v2])
                {
                    if(v1>=0&&v1<=r&&v2>=0&&v2<=c&&graph[v1][v2]==0)
                    {
                        level[v1][v2]=level[f1][f2]+1;
                        //cout<<"LEVEL:"<<level[v1][v2]<<endl;
                        q.push(v1);
                        q.push(v2);
                        visited[v1][v2]=true;
                        if(v1==enx&&v2==eny)
                            ans=level[v1][v2];
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

UVa 336 - A Node Too Far

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int edges,cas=1;
    while(cin>>edges)
    {
        if(edges==0)
            break;
        vector<long long int>nodes[100000];
        map<long long ,int>difference;
        difference.clear();
        int i,j,a,b,num=0;
        for(i=0;i<edges;i++)
        {
            cin>>a>>b;
            nodes[a].push_back(b);
            nodes[b].push_back(a);
            if(difference[a]!=1)
            {
                difference[a]=1;
                num++;
            }
            if(difference[b]!=1)
            {
                difference[b]=1;
                num++;
            }
        }
        map<long long ,int>visited;
        map<long long ,int>level;
        visited.clear();
        level.clear();
        int start,ttl;
        int number;
        queue<long long int>q;
        //int c=0;
        while(cin>>start>>ttl)
        {
            if(start==0 && ttl==0)
                break;
            number=0;
            visited.clear();
            visited[start]=1;
            level[start]=0;
            q.push(start);
            while(!q.empty())
            {
                int front=q.front();
                q.pop();
                int l=nodes[front].size();
                for(i=0;i<l;i++)
                {
                    if(visited[nodes[front][i]]!=1)
                    {
                        level[nodes[front][i]]=level[front]+1;
                        if(level[nodes[front][i]]>ttl)
                        {
                            break;
                        }
                        number++;
                        visited[nodes[front][i]]=1;
                        q.push(nodes[front][i]);
                    }
                }
                //q.pop();
            }
            printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",cas,num-number-1,start,ttl);
            cas++;
        }
    }
    return 0;

}

UVa 567 - Risk

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int cas=1,nn;
    while(cin>>nn)
    {
        vector<int>nodes[1000];
        int i,j,k,l,m,n,a,b;
        for(i=0;i<nn;i++)
        {
            cin>>a;
            b=1;
            nodes[b].push_back(a);
            nodes[a].push_back(b);
        }
        for(i=1;i<19;i++)
        {
            cin>>nn;
            b=i+1;
            for(j=0;j<nn;j++)
            {
                cin>>a;
                nodes[a].push_back(b);
                nodes[b].push_back(a);
            }
        }
        int node1,node2;
        cin>>m;
        {
            cout<<"Test Set #"<<cas<<endl;
            cas++;
            for(i=0;i<m;i++)
            {
                cin>>node1>>node2;
                queue<int>q;
                bool visited[1000];
                memset(visited,0,sizeof(visited));
                int level[1000];
                //memset(visited,0,sizeof(visited));
                int ans,node;
                visited[node1]=true;
                level[node1]=0;
                q.push(node1);
                while(!q.empty())
                {
                    int f=q.front();
                    for(j=0;j<nodes[f].size();j++)
                    {
                        int v=nodes[f][j];
                        if(visited[v]==false)
                        {
                            level[v]=level[f]+1;
                            visited[v]=true;
                            q.push(v);
                        }
                        if(v==node2)
                        {
                            //cout<<55555555<<endl;
                            ans=level[v];
                        }
                    }
                    q.pop();
                }
                printf("%2d to %2d: %d\n",node1,node2,ans);
            }

        }
        cout<<endl;
    }
    return 0;
}

UVa 10004 - Bicoloring

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int i,j,k,l,m,n,x,y,test;
    while(cin>>test)
    {
        queue<int>q;
        int color[1000];
        vector<int>nodes[1000];
        if(test==0)
            break;
        else
        {
            bool flag=true;
            cin>>n;
            for(i=0;i<n;i++)
            {
                cin>>x>>y;
                nodes[x].push_back(y);
                nodes[y].push_back(x);
            }
            memset(color,-1,sizeof(color));
            color[0]=0;
            q.push(0);
            while(!q.empty())
            {
                x=q.front();
                q.pop();
                l=nodes[x].size();
                for(i=0;i<l;i++)
                {
                    if(color[nodes[x][i]]==-1)
                    {
                        if(color[x]==0)
                        {
                            color[nodes[x][i]]=1;
                        }
                        else
                        {
                            color[nodes[x][i]]=0;
                        }
                        q.push(nodes[x][i]);
                    }
                    else
                    {
                        if(color[nodes[x][i]]==color[x])
                        {
                            flag=false;
                            break;
                        }
                    }
                }
                if(flag==false)
                break;
            }
            if(flag)
                cout<<"BICOLORABLE."<<endl;
            else
                cout<<"NOT BICOLORABLE."<<endl;
        }
    }
    return 0;
}

Light OJ 1056 (Olympic)

#include<bits/stdc++.h>
#define pi acos(-1.0)
using namespace std;
int main()
{
    long long int i,j,k,l,m,n,test;
    double angle,a,b,slice,rad,d,len,wide,rat;
    char ch;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>a>>ch;
        cin>>b;
        rad=sqrt(((a/2.0)*(a/2.0))+((b/2.0)*(b/2.0)));
        angle=acos((2.0*rad*rad-b*b)/(2.0*rad*rad));
        slice=rad*angle;
        rat=400.0/(2.0*(a)+2.0*slice);
        len=a*rat;
        wide=b*rat;
        printf("Case %lld: %.8f %.8f\n",k,len,wide);
    }
    return 0;
}

Light OJ 1112 (Ekka Dokka)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int i,j,x,w,n,k;
    cin>>n;
    for(k=1;k<=n;k++)
    {
        bool flag=0;
        cin>>w;
        if(w%2==1)
            cout<<"Case "<<k<<": "<<"Impossible"<<endl;
        else
        {
           
            for(i=2;i<=(w/2);i=i*2)
            {
                if((w/i)%2==1&&((w/i)*i)==w)
                {
                flag=1;
                break;
                }
            }
            if(flag==1)
                cout<<"Case "<<k<<": "<<(w/i)<<" "<<i<<endl;
            else
                cout<<"Case "<<k<<": "<<"Impossible"<<endl;
        }
    }
    return 0;
}

UVa 1225 - Digit Counting

#include<bits/stdc++.h>
using namespace std;
int main()
{
    char s[110];
    long long int num[100][100],sum[1000],i=0,l,j,n=0,index,temp,rem,m=999,start;
    for(i=0;i<100;i++)
    {

        for(j=0;j<100;j++)
        {
            num[i][j]=0;
        }
    }
    for(i=0;i<1000;i++)
        sum[i]=0;
    while(1)
    {
        scanf("%s",s);
        if(s[0]=='0')
            break;
        else
        {
            l=strlen(s);


            for(j=99;j>=0;j--)
            {
                if(l>0)
                {
                    num[n][j]=s[l-1]-48;
                }
                l--;
            }
            n++;

        }
    }
    temp=0;
    rem=0;
    for(i=99;i>=0;i--)
    {

        for(j=99;j>=0;j--)
        {
            temp=temp+num[j][i];

        }
        temp=temp+rem;
        sum[m]=temp%10;
        temp=temp/10;
        m=m-1;
    }
    for(i=0;i<1000;i++)
    {
        if(sum[i]!=0)
        {
            start=i;
            break;
        }
    }
    for(i=start;i<1000;i++)
        cout<<sum[i];
    cout<<endl;
    return 0;
}

UVa 713 - Adding Reversed Numbers

#include<bits/stdc++.h>
using namespace std;
int main()
{
    char num1[400],num2[400],res[400];
    int test,i,j,k,l1,l2,temp,a[400],b[400],c[400],x,y,z,pos,pos1,d[400];
    cin>>test;
    for(k=1;k<=test;k++)
    {
        x=y=399;
        temp=0;
        z=0;
        for(i=0;i<400;i++)
        {
            a[i]=b[i]=c[i]=0;
        }
        scanf("%s %s",num1,num2);
        l1=strlen(num1);
        l2=strlen(num2);
        for(i=0;i<l1;i++)
        {
            a[x--]=num1[i]-48;
        }
        for(i=0;i<l2;i++)
        {
            b[y--]=num2[i]-48;
        }
        for(i=399;i>=0;i--)
        {
            temp=temp+a[i]+b[i];
            c[i]=temp%10;
            temp=temp/10;
        }
        for(i=0;i<400;i++)
        {
            if(c[i]!=0)
            {
                pos=i;
                break;
            }
        }
        for(i=399;i>=pos;i--)
        {
            d[z++]=c[i];
        }
        for(i=0;i<z;i++)
        {
            if(d[i]!=0)
            {
                pos1=i;
                break;
            }
        }
        for(i=pos1;i<z;i++)
        {
            cout<<d[i];
        }
        cout<<endl;
    }
    return 0;
}

UVa 12157 - Tariff Plan

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int test,n,mile[100],juice[100],i,j,k,m,mcost,jcost,rem;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        mcost=jcost=0;
        cin>>n;
        for(i=0;i<n;i++)
        {
            cin>>mile[i];
            juice[i]=mile[i];
        }
        for(i=0;i<n;i++)
        {
            m=((mile[i]-1)/30)+1;
            rem=mile[i]%30;
            if(rem==0)
            {
                mile[i]=m+1;
            }
            else
            {
                mile[i]=m;
            }

        }
        for(i=0;i<n;i++)
        {
            m=(juice[i]-1)/60+1;
            rem=juice[i]%60;
            if(rem==0)
            {
                juice[i]=m+1;
            }
            else
            {
                juice[i]=m;
            }

        }
        for(i=0;i<n;i++)
        {
            mcost=mcost+mile[i]*10;
            jcost=jcost+juice[i]*15;
        }
        if(mcost<jcost)
            printf("Case %d: Mile %d\n",k,mcost);
        else if(mcost>jcost)
            printf("Case %d: Juice %d\n",k,jcost);
        else
            printf("Case %d: Mile Juice %d\n",k,mcost);
    }
    return 0;
}

UVa 11805 - Bafana Bafana

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,n,p,test,i,j,k,l,ans;
    cin>>test;
    for(l=1;l<=test;l++)
    {
        cin>>n>>k;
        cin>>p;
        for(i=k;i<=(k+p);i++)
        {
            a=i;
        }
        ans=a%n;
        printf("Case %d: ",l);
        if(ans==0)
            cout<<n<<endl;
        else
            cout<<ans<<endl;
    }
    return 0;
}

UVa 10922 - 2 the 9s

#include<bits/stdc++.h>
using namespace std;
int rec(int sum)
{
    int rem,S=0;
    while(sum)
    {
        S=S+(sum%10);
        sum=sum/10;
    }
    return S;
}
int main()
{
    char a[2000];
    int b[2000],i,j,k,n,l,sum,count,res,S;
    while(1)
    {
        sum=0;
        count=1;
        S=0;
        scanf("%s",a);
        if(a[0]=='0'&&strlen(a)==1)
            break;
        else
        {
            l=strlen(a);
            for(i=0;i<l;i++)
            {
                b[i]=a[i]-48;
            }
            for(i=0;i<l;i++)
            {
                sum=sum+b[i];
            }

            if(sum%9==0)
            {
                while(sum>9)
                {
                    count++;
                    S=0;
                    while(sum>0)
                    {
                        S=S+sum%10;
                        sum=sum/10;
                    }
                    sum=S;
                }
                printf("%s is a multiple of 9 and has 9-degree %d.\n",a,count);
            }
            else
            {
            printf("%s is not a multiple of 9.\n",a);
            }

        }
    }
    return 0;
}

UVa 10346 - Peter's Smokes

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,k,rem,butt,sum;
    while(cin>>n>>k)
    {
        butt=(n/k)+(n%k);
        sum=(n/k);

        while(butt>=k)
        {
            sum=sum+(butt/k);
            butt=(butt/k)+(butt%k);
        }

        cout<<(sum+n)<<endl;
    }
    return 0;
}

Breadth First Search (BFS)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    vector<int>nodes[1000];
    int i,j,edges,a,b;
    cin>>edges;
    for(i=0;i<edges;i++)
    {
        cin>>a>>b;
        nodes[a].push_back(b);//INSERTING ELEMENTS
        nodes[b].push_back(a);
    }
    for(i=0;i<100;i++)
    {
        if(!nodes[i].empty())
        {
            cout<<"("<<i<<") : ";
            for(vector<int>::iterator it=nodes[i].begin();it!=nodes[i].end();++it)//ITERATOR TRAVERSES ALL ELEMENTS UNDER A NODE
            {
                cout<<*it<<" ";
            }
            cout<<endl;
        }
    }
    queue<int>q;
    bool visited[1000];
    int start,level[1000],parent[1000];
    cin>>start;//STARTING NODE
    memset(visited,0,sizeof(visited));
    visited[start]=1;//STARTING NODE IS ALREADY VISITED WHEN TAKEN AS INPUT
    q.push(start);
    level[start]=0;//LEVEL OF STARTING NODE IS ZERO
    while(!q.empty())
    {
        int front=q.front();
        cout<<front<<" ";
        for(vector<int>::iterator it=nodes[front].begin();it!=nodes[front].end();++it)
        {
            if(!visited[*it])
            {
                visited[*it]=1;//VISITING ALL ELEMENTS OF A NODE
                level[*it]=level[front]+1;//INCREASING 1 LEVEL FROM PARENT NODE
                parent[*it]=front;//PUTTING NEXT NEARING NODE OF PARENT AS PARENT
                q.push(*it);//INSERTING NODES IN THE QUEUE
            }
        }
        q.pop();//DELETING CURRENT FRONT PARENT NODE AND INITIALINZE THE NEXT NODE AS PARENT
    }
    return 0;

}

Light OJ 1014 Ifter Party

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int a[100000],i,j,k,l,m,n,test,p,x;
    cin>>test;
    for(x=1;x<=test;x++)
    {
        k=0;
        cin>>p>>l;
        cout<<"Case "<<x<<":";
        if((p-l)<=l)
            cout<<" impossible"<<endl;
        else
        {
            for(i=1;i<=sqrt(p-l);i++)
            {
                if((p-l)%i==0)
                {
                    if((p-l)%i==0)
                    {
                        a[k++]=i;
                    }
                    if(((p-l)/i) != i)
                    {
                        a[k++]=(p-l)/i;
                    }
                }
            }
            sort(a,a+k);
            for(int m=0;m<k;m++)

            {
                if(a[m]>l)
                cout<<" "<<a[m];
            }

            cout<<endl;

        }
    }
}

Light OJ 1028 Trailing Zeroes (I)

#include<bits/stdc++.h>
using namespace std;
#define max 1000009
bool prime[max];
long long int num[max];
int main()
{
    long long int i,j,n,k,x,px,l,test,p,q,m,ans,counter;
    char a[100];
    for(i=4;i<=max;i+=2)
        prime[i]=1;

    long long int s=sqrt(max);
    for(i=3;i<=s;i+=2)
    {

        if(prime[i]==0)
        {
            for(j=i*i;j<=max;j+=2*i)
            {
                prime[j]=1;
            }
        }
    }
    prime[1]=1;prime[0]=1;
    k=0;
    for(i=0;i<max;i++)
    {
        if(prime[i]==0)
        {
            num[k++]=i;
        }
    }
    cin>>test;
    for(m=1;m<=test;m++)
    {
        scanf("%lld",&n);
        ans=1;
        for(int j=0;j<k&&num[j]<=sqrt(n);j++)
        {
            if(n<num[j])
                break;
            if(n%num[j]==0)
            {
                counter=1;
                while(n%num[j]==0)
                {
                    n/=num[j];
                    counter++;
                }
                ans*=counter;
            }
        }
        if(n>1)
        {
            ans=ans*2;
        }
        printf("Case %lld: %lld\n",m,ans-1);
    }
    return 0;
}

Light OJ 1189 Sum of Factorials

#include<bits/stdc++.h>
using namespace std;
long long int fact(int n)
{
    if(n==1)
        return 1;
    else if(n==0)
        return 1;
    else
        return n*fact(n-1);
}
int main()
{
    long long int n,i,j,k,l,m,test,a[25],b[25];
    a[0]=1;
    for(i=1;i<=20;i++)
    {
        a[i]=fact(i);
    }
    cin>>test;
    for(j=1;j<=test;j++)
    {
        cin>>n;
        cout<<"Case "<<j<<": ";
        if(n==1)
            cout<<"1!"<<endl;
        else if(n==2)
            cout<<"2!"<<endl;
        else if(n==3)
            cout<<"1!+2!"<<endl;
        else
        {
            k=0;
            bool flag=1;
            for(i=20;i>=0;i--)
            {
                if(n<a[i])
                {
                    continue;
                }
                if(n>=a[i])
                {
                    n=n-a[i];
                    b[k++]=i;
                }
                if(n==0)
                {
                    flag=1;
                    break;
                }
                if(n<0||(n!=0&&i==0))
                {
                    flag=0;
                    break;
                }
            }
            if(flag==1)
            {
                sort(b,b+k);
                for(i=0;i<k;i++)
                {
                    cout<<b[i]<<"!";
                    if(i!=k-1)
                        cout<<"+";
                }
                cout<<endl;
            }
            else
            {
                cout<<"impossible"<<endl;
            }
        }
    }
    return 0;
}

Light OJ 1112 Curious Robin Hood

#include<bits/stdc++.h>
#define M 1000009
using namespace std;
int arr[M];
int tree[4*M];
void init(int node,int b,int e)
{
    if(b==e)
    {
        tree[node]=arr[b];
        return;
    }
    int left=2*node;
    int right=left+1;
    int mid=(b+e)/2;
    init(left,b,mid);
    init(right,mid+1,e);
    tree[node]=tree[left]+tree[right];
}
int query(int node,int b,int e,int i,int j)
{
    if(i>e||j<b)
        return 0;
    if(b>=i&&e<=j)
    {
        return tree[node];
    }
    int left=2*node;
    int right=left+1;
    int mid=(b+e)/2;
    int p1=query(left,b,mid,i,j);
    int p2=query(right,mid+1,e,i,j);
    return (p1+p2);
}
void update(int node,int b,int e,int i,int newvalue)
{
    if(i>e||i<b)
        return;
    if(b>=i&&e<=i)
    {
        tree[node]=newvalue;
        return;
    }
    int left=2*node;
    int right=left+1;
    int mid=(b+e)/2;
    update(left,b,mid,i,newvalue);
    update(right,mid+1,e,i,newvalue);
    tree[node]=tree[left]+tree[right];
}
int main()
{
    int test;
    scanf("%d",&test);
    for(int k=1;k<=test;k++)
    {
        int m,n;
        scanf("%d %d",&n,&m);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&arr[i]);
        }
        printf("Case %d:\n",k);
        init(1,0,n-1);
        for(int j=1;j<=m;j++)
        {
            int option;
            scanf("%d",&option);
            if(option==1)
            {
                int index;
                scanf("%d",&index);
                printf("%d\n",arr[index]);
                arr[index]=0;
                update(1,0,n-1,index,arr[index]);
            }
            else if(option==2)
            {
                int index,amount;
                scanf("%d %d",&index,&amount);
                arr[index]=arr[index]+amount;
                update(1,0,n-1,index,arr[index]);
            }
            else
            {
                int a,b;
                scanf("%d %d",&a,&b);
                printf("%d\n",query(1,0,n-1,a,b));
            }
        }
    }
    return 0;
}

Light OJ 1215 Finding LCM

#include<bits/stdc++.h>
#define mx 10000000
using namespace std;
bool prime[mx];
int arr[700000],l;
void sieve()
{
    long long int i,j;
    l=0;
    for(i=4;i<=mx;i+=2)
        prime[i]=1;
    int s=sqrt(mx);
    for(i=3;i<=s;i+=2)
    {
        if(prime[i]==0)
        {
            for(j=i*i;j<=mx;j+=2*i)
            {
                prime[j]=1;
            }
        }
    }
    prime[1]=1;prime[0]=1;
    for(i=0;i<=mx;i++)
    {
        if(prime[i]==0)
            arr[l++]=i;
    }
}
long long int count_pf(long long int a,long long int b,long long int c)
{
    long long int i,j,counta,countb,countc,m,ans=1;
    for(i=0;;i++)
        {
            if(arr[i]>c)
                break;
            counta=0;
            countb=0;
            countc=0;
            m=arr[i];
            if(c%m==0)
            {
                while(1)
                {
                    if(c%m==0)
                    {
                        c=c/m;
                        countc++;
                    }
                    else
                        break;
                    if(a%m==0)
                    {
                        a=a/m;
                        counta++;
                    }
                    if(b%m==0)
                    {
                        b=b/m;
                        countb++;
                    }
                }
                if(max(counta,countb)<countc)
                {
                 
                    for(j=1;j<=countc;j++)
                    {
                        ans=ans*m;
                    }
                }

            }
        }
        return ans;
}
int main()
{
    sieve();
    long long int i,j,k,m,n,p,A,B,C,LCM,test,count,ans;
    cin>>test;
    for(k=1;k<=test;k++)
    {
        cin>>A>>B;
        cin>>LCM;
        cout<<"Case "<<k<<": ";
        if(LCM%A!=0||LCM%B!=0)
        {
            cout<<"impossible"<<endl;
        }
        else
        {
            cout<<count_pf(A,B,LCM)<<endl;
        }
    }
    return 0;
}