PROBLEM LINK:
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();
}