ACM ICPC Preliminary 2016 Team Practice Contest A.Multiplication Queries

Problem Link: A - Multiplication Queries 

//Next Codeforces Round #354 (Div. 2)
#include<bits/stdc++.h>

//#include<cstdio>
//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<cstring>
//#include<cmath>
//#include<map>

using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
//#define i64 long long
#define high 50005

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;

LL ar[high], br[high];
LL tree[high * 3] , m;

LL multiple(LL a, LL b , LL c)
{
    if(!b) return 0;

    LL x = multiple(a , b/2, c)%c;

    if(!(b&1))
    {
        return ((x%c) + (x%c))%c;
    }

    else
    {
        return ((a%c) + (x%c)+(x%c))%c;
    }
}

LL bigmod(LL a, LL b , LL c)
{
    if(!b) return 1;

    LL x = bigmod(a , b/2, c)%c;

    if(!(b&1))
    {
        return multiple(x , x , c);
    }

    else
    {
        return (multiple(a%c, multiple(x , x , c)%c , c))%c;
    }
}

void build(LL node, LL b , LL e)
{
    if(b == e)
    {
        tree[node] = br[b];
        return;
    }

    LL Left = node * 2;
    LL Right = (node * 2)+1;
    LL mid = (b + e) / 2;

    build(Left , b , mid);
    build(Right, mid+1, e);

    tree[node] = (tree[Left]%m * tree[Right]%m)%m;
}

LL query(LL node, LL b , LL e, LL i, LL j)
{
    if(i > e or j < b) return 1;

    if(b >= i and e <= j)
    {
        //cout << tree[node] << "; ";
        return tree[node];
    }

    LL Left = node * 2;
    LL Right = (node * 2) + 1;
    LL mid = (b + e) / 2;

    LL pek = query(Left, b , mid, i , j);
    LL pdui = query(Right, mid+1, e , i , j);

    //cout << pek << " " << pdui << "; ";

    return (pek%m * pdui%m)%m;
}

int main()
{
    fast;
    int t , tc=0;
    LL n , q , k , i , l , r, tmp=1 , p;
    //cin >> t;
    sf("%d", &t);
    while(t--)
    {
        //cin >> n >> q >> k >> m;
        //ans.clear();
        sf("%lld %lld %lld %lld", &n, &q, &k ,&m);

        for(i=1; i<=n; i++)
        {
            //cin >> ar[i];
            sf("%lld", &ar[i]);
        }

        br[0] = 1;

        for(i=1; i<=n; i++)
        {
            br[i] = bigmod(ar[i] , k , m);

            //br[i]= (br[i]%m * br[i-1]%m)%m;
        }

        build(1 , 1 , n);

        //for(i=1; i<=n; i++) cerr << tree[i] << " ";

        pf("Case %d:\n", ++tc);

        while(q--)
        {
            sf("%lld %lld", &l, &r);

            LL ans = query(1, 1, n, l , r);
            pf("%lld\n", ans%m);
        }

      }

    return 0;
}