WINIT - Editorial

PROBLEM LINK:

(Contest Page | CodeChef)

Author: Ashish Vishal
Tester: Aman Singh
Editorialist: Aditya Kumar Singh

DIFFICULTY:

Medium-Hard

PREREQUISITES:

Data Structure, maths, number theory

PROBLEM:

In this Problem:-
For the first query, we have to update the array element at any given index.
For the second query, we have to find the Euler totient of the product of numbers of array from index L to R .

EXPLANATION:

Here, if d=product of number of the array from index L to R (included both L and R), then we can find the Euler totient of d using it’s prime factors, if d = (p1a1) * (p2a2) * … (pkak), where Pi is the ith prime factor and ai is the frequency of the corresponding primes.
So, \phi(d) = ((p1(a1-1))(p1-1)) * ((p2(a2-1))(p2-1))*… ((pk(ak-1))(pk-1))

where \phi(d)=euler totient of d.
For calculating Euler totient of d, we have to find the prime factor of d and the frequency of that prime factors.
In the problem, the number of different factors of all the numbers in the array at any instant will be less than or equal to 10, and after each update query of type 1, we have to maintain the 10 different prime number which is present in the array. Here, we can use SPF to calculate prime factor of each number in logarithmic time. Using segment tree or BIT for 10 different primes we can count the total number of occourence of that prime in logarithmic time, and can also do update in logarithmic time.
Time complexity:- k*O((n+m)log(size of BIT)), where k is a constant

SOLUTIONS:

Setter’s Solution
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define rep(i,a,b) for(long long i=a;i<b;i++)
typedef long long int ll;
typedef vector<ll> vi;
 
const ll mod=1000000007;
int ma[1000001],rma[11],p_freq[1000001];
vi A(200001),bit[11],fact[1000001];
 
 
void preprocess()// storing prime factor of number in fact variable
{
    vector<bool> prime(1000001,1);
	prime[0]=0;prime[1]=0;
	for(ll i=2;i<=1000000;i++)
	{
		if(prime[i])
		{
		    fact[i].pb(i);
			for(ll j=2*i;j<=1000000;j+=i)
			{
				prime[j]=0;
				fact[j].pb(i);
			}
		}
	}
}
// update the binary indexed tree
void update(ll x,ll sig,ll ind)
{
    for(int i=0;i<fact[x].size();i++)
    {
        ll num=x,div=fact[x][i],freq=0;
 		// mapping the different prime factors in range of 1 to 10
        if(p_freq[div]==0)
        {
            for(int j=1;j<11;j++)
            {
                if(p_freq[rma[j]]==0)
                {
                    ma[div]=j;
                    rma[j]=div;
                    break;
                }
            }
        }
        // to calculat the frequency of prime factor(div) in num
        while(num%div==0)
        {
            freq++;
            num/=div;
        }
        
        // adding or substracting the frequency of prime factor of number 
        if(sig==0)
            p_freq[div]+=freq;
        else
            p_freq[div]-=freq;

        // updating the frequency of prime factor in binary indexed tree
        for(int j=ind;j<=1000000;j+=(j&-j))
        {
            if(sig==0)
                bit[ma[div]][j]+=freq;
            else
                bit[ma[div]][j]-=freq;
        }
    }
}

// to calculate the sum of numbers of an array from index 1 to x of ith binary indexed tree.
ll sum_query(ll i,ll x)
{
    ll sum=0;
    while(x>0)
    {
        sum+=bit[i][x];
        x-=(x&-x);
    }
    return sum;
}
// Modular exponentiation to calculate the (a^x)%m
ll modpow(ll a,ll x,ll m)
{
    if(x==0)return 1%m;
    ll ans=modpow(a,x/2,m);
    ans=(ans*ans)%m;
    if(x%2)
        ans=(ans*a)%m;
    return ans;
}
ll find_ans(ll l,ll r)
{
    ll ans=1;
    for(int i=1;i<=10;i++)
    {
        ll sum=(sum_query(i,r)-sum_query(i,l-1))%mod;// calculate the total occourence of a prime from index l to r.
        if(sum>0)
        {
            ll tot=(modpow(rma[i],sum-1,mod)*(rma[i]-1))%mod;// using formula to calculate the euler totient
            ans=(ans*tot)%mod;
        }
    }
   return ans;
}
 
void solve()
{
 
    for(int i=0;i<=10;i++)// initialising binary indexeed tree
        bit[i].resize(1000001,0);
    ll n,m;
    cin>>n>>m;
 
    for(int i=1;i<=n;i++)
    {
        cin>>A[i];
        update(A[i],0,i);//increasing the prime factors's count of array elment at index i.
    }
    for(int i=0;i<m;i++)
    {
        ll t;
        cin>>t;
        if(t==1)
        {
            ll x,y;
            cin>>x>>y;
            update(A[x],1,x);//deleting the prime factors's count of array elment at index x before update.
            A[x]=y;
            update(A[x],0,x);//increasing the prime factors's count of array elment at index x after update.
        }
        else
        {
            ll l,r;
            cin>>l>>r;
            ll ans=find_ans(l,r);//calculate the euler totient of product of numbers of arra from index l to r.
            cout<<ans<<endl;
        }
    }
}
int32_t main()
{
    fast;// fast input output
    preprocess();//storing the prime factors of all numbers from 1 to 1000000
    solve();
} 
2 Likes

This problem can be solved with ordered statistics too. Messes up with ordered statistics during the contest -_-

Hey @adikr_singh,

I am using segment trees almost as you have specified bu I am getting WA

Can you please tell me the test case where my code is going wrong ?

UPD: I got the issue, there was some problem in my implementation.

1 Like