Hackerrank: Solve the Queries!

Problem Link : https://www.hackerrank.com/contests/womens-codesprint-4/challenges/solve-the-queries

Solution Idea:

    The main observation in this problem is the given numbers are <=100 and there are 25 prime number less than 100. As we need to answer whether a range multiplication is multiple of another range multiplication or not.

    We know when we multiply two number their prime power is added. For example 12*18 = (2^2 * 3^1) * (2^1 * 3^2)
    = (2^(2+1) * 3^(1+2))
    = (2^3 * 3^3)
    = 216

    So we can store prime factors of every given number in each segment tree leaf. And while merging two leaf node we need to add each prime power between two two leafs. So a node in the segment tree hold the information about the nubmer in the subtree of this node has how many ith prime divisor.

    Now for each query we can get the power factor of each range from the segment tree and check whether they divides or not and produce the required answer from this prime factors.



#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define LINE_PRINT_CASE  printf("Case %d:\n",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

int prime[30]= {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int mp[100];

#define mx 50005
#define segment_tree int l=n*2,r=l+1,mid=(b+e)/2
struct data
{
    int lazy;
    int ara[25];
};

data ret;

int numbers[mx];
data tree[3*mx];

void func(int n, data &temp, int mul)
{
    ms(temp.ara,0);
    for(int i=0; i<25 && prime[i]*prime[i]<=n; i++)
    {
        if(n%prime[i]==0)
        {
            while(n%prime[i]==0)
            {
                n/=prime[i];
                temp.ara[i]++;
            }
            temp.ara[i]*=mul;
        }
    }

    if(n>1)
        temp.ara[mp[n]]+=mul;
}

void push_up(data &a, data &b, data &c)
{
    for(int i=0; i<25; i++)
        a.ara[i]=b.ara[i]+c.ara[i];
}

void push_down(int n, int b, int e)
{
    if(tree[n].lazy)
    {
        segment_tree;
        func(tree[n].lazy,tree[l],mid-b+1);
        func(tree[n].lazy,tree[r],e-mid);
        tree[l].lazy=tree[n].lazy;
        tree[r].lazy=tree[n].lazy;
        tree[n].lazy=0;
    }
}

void init(int n, int b, int e)
{
    if(b==e)
    {
        tree[n].lazy=0;
        func(numbers[b],tree[n],1);
        return;
    }
    segment_tree;
    init(l,b,mid);
    init(r,mid+1,e);
    push_up(tree[n],tree[l],tree[r]);
}

void update(int n, int b, int e, int i, int j, int val)
{
    if(b>j || e<i) return;
    if(b>=i && e<=j)
    {
        func(val,tree[n],e-b+1);
        tree[n].lazy=val;
        return;
    }
    segment_tree;
    push_down(n,b,e);
    update(l,b,mid,i,j,val);
    update(r,mid+1,e,i,j,val);
    push_up(tree[n],tree[l],tree[r]);
}

data query(int n, int b, int e, int i, int j)
{
    if(b>j || e<i) return ret;
    if(b>=i && e<=j)
    {
        return tree[n];
    }
    push_down(n,b,e);
    segment_tree;
    data p=query(l,b,mid,i,j);
    data q=query(r,mid+1,e,i,j);
    data xx;
    push_up(xx,p,q);
    return xx;
}

ll bigmod(ll n, ll pow, ll mod)
{
    ll rett=1;
    while(pow)
    {
        if(pow%2)
            rett=(rett*n)%mod;
        n=(n*n)%mod;
        pow/=2;
    }
    return rett;
}

int main()
{

//    freopen("in.txt","r",stdin);
//	  freopen("out.txt","w",stdout);
    for(int i=0; i<25; i++) mp[prime[i]]=i;

    int n;
    sf(n);
    loop1(i,n) sf(numbers[i]);

    init(1,1,n);

    int q;
    sf(q);
    while(q--)
    {
        int a;
        sf(a);
        if(a==1)
        {
            int l,r,x;
            sfff(l,r,x);
            update(1,1,n,l,r,x);
        }
        else
        {
            int l, r, p, q, m;
            sff(l,r);
            sff(p,q);
            sf(m);

            data x=query(1,1,n,l,r);
            data y=query(1,1,n,p,q);
            bool valid=1;
            for(int i=0; i<25 && valid; i++)
            {
                x.ara[i]-=y.ara[i];
                if(x.ara[i]<0)
                    valid=0;
            }

            if(valid==0)
            {
                printf("-1\n");
                continue;
            }

            ll ans=1;

            for(int i=0;i<25;i++)
            {
                if(x.ara[i])
                {
                    ans*=bigmod(prime[i],x.ara[i],m);
                    ans%=m;
                }
            }

            printf("%lld\n",ans);

        }
    }


    return 0;
}

Advertisements