PROBLEM LINK:
Author: Satyam Gupta
Tester: Pulkit Sharma
Editorialists: Satyam Gupta
DIFFICULTY:
MEDIUM
PREREQUISITES:
Segment Tree with Lazy Propagation, Number Theory
PROBLEM:
You are given N integers, denoted by A_1, A_2, … , A_N
Now you are given Q queries, each of whom is of following two types:
Type 1: 1 L R: Print the no. of trailing zeros (zeros in the end) in the multiplication of no.s in range [L,R] of array A[], i.e. no. of zeros in A_L * A_{L+1} * … * A_R
Type 2: 2 L R V: Multiply the all the numbers in range [L,R] with V.
EXPLANATION:
A number has trailing zeros equal to the no. of times it can be divided by 10 with remainder 0. Since 10 = 2*5, in other words we can say that a number has trailing zeros equal to the no. of times it can be divided by both 2 and 5 with remainder 0. So, we don’t need the number itself rather the no. of times it can be divided by 2 and 5 with remainder 0. So, if a number can be divided by ‘2’ for x times and by ‘5’ for y times, then that no. will have min(x,y) trailing zeros.
Since any element of array can go only upto 2000, we can calculate the no. of times a number can be divided by 2 and 5 for all numbers from 1 to 2000 using this pseudo-code:
for i=1 to 2000:
div2[i]=0
div5[i]=0
x=i
while x%2==0 :
div2[i]=div2[i]+1
x=x/2
while x%5==0 :
div5[i]=div5[i]+1
x=x/5
In other words div2[i] = no. of times 2 appear in prime factorization of i and similarly div5[i] = no. of times 5 appear in prime factorization of i
Now for example,
1500 = 2*2*3*5*5*5
So, div2[1500]=2 and div5[1500]=3
then, no. of trailing zeros in 1500 = min(2,3) = 2
Then for no. of trailing zeros in the multiplication of no.s in range [L,R],
x=div2[A_L]+div2[A_{L+1}]+...+div2[A_R]
y=div5[A_L]+div5[A_{L+1}]+...+div5[A_R]
No. of trailing zeros = min(x,y)
Since we need to work on ranges, we can use segment tree. For each node that represents range [L,R] we need to keep sum of the div2 and div5 from A_L to A_R.
For merging left and right nodes into the parent node, refer to the pseudo-code below:
merge(parent,left,right):
parent.two = left.two + right.two
parent.five = left.five + right.five
Because update queries over ranges, we need to use lazy propagation on segment tree.
For type 2 queries of form (2 L R V), we will store the changes to be made (i.e. adding div2[V] and div5[V] to the node members “two” and “five” respectively of range [L,R]) seperately and then later during the Type 1 query, update the tree as needed.
Complexity of this solution:
For preprocessing O(NlogN) and for each query O(logN)
Final complexity = O(NlogN + QlogN)
AUTHOR’S AND TESTER’S SOLUTIONS:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define N 100000
#define MAX 500000
struct Tree_Node
{
int two,five;
} tree[MAX],lazy[MAX],arr[N],dummy;
int div2[2005],div5[2005];
void build(int node, int a, int b)
{
if(a > b) return;
lazy[node].two=lazy[node].five=0;
// Init Values
if(a == b)
{
tree[node].two = arr[a].two;
tree[node].five = arr[a].five;
//cout<<a<<" "<<b<<"node:"<<node<<endl;
return;
}
int lt=node<<1;
int rt=lt+1;
build(lt, a, (a+b)/2);
build(rt, 1 + ((a+b)/2), b);
//Init Internal nodes
tree[node].two = tree[lt].two + tree[rt].two;
tree[node].five = tree[lt].five + tree[rt].five;
}
void update(int node, int a, int b, int i, int j, Tree_Node val)
{
int lt=node<<1; //left child = node*2
int rt=lt+1; //right child = node*2 + 1
if(lazy[node].two != 0 || lazy[node].five != 0)
{
tree[node].two += lazy[node].two * (b-a+1);
tree[node].five += lazy[node].five * (b-a+1);
if(a != b)
{
lazy[lt].two += lazy[node].two;
lazy[lt].five += lazy[node].five;
lazy[rt].two += lazy[node].two;
lazy[rt].five += lazy[node].five;
}
lazy[node].two = lazy[node].five = 0;
}
if(a > b || a > j || b < i)
return;
if(a >= i && b <= j)
{
tree[node].two += val.two * (b-a+1);
tree[node].five += val.five * (b-a+1);
if(a != b)
{
lazy[lt].two += val.two;
lazy[lt].five += val.five;
lazy[rt].two += val.two;
lazy[rt].five += val.five;
}
return;
}
update(lt, a, (a+b)/2, i, j, val);
update(rt, 1+(a+b)/2, b, i, j, val);
tree[node].two = tree[lt].two + tree[rt].two;
tree[node].five = tree[lt].five + tree[rt].five;
}
Tree_Node query(int node, int a, int b, int i, int j)
{
int lt=node<<1;
int rt=lt+1;
if(a > b || a > j || b < i) return dummy;
if(lazy[node].two != 0 || lazy[node].five != 0)
{
tree[node].two += lazy[node].two * (b-a+1);
tree[node].five += lazy[node].five * (b-a+1);
if(a != b)
{
lazy[lt].two += lazy[node].two;
lazy[lt].five += lazy[node].five;
lazy[rt].two += lazy[node].two;
lazy[rt].five += lazy[node].five;
}
lazy[node].two = lazy[node].five = 0;
}
if(a >= i && b <= j)
return tree[node];
Tree_Node q1 = query(lt, a, (a+b)/2, i, j);
Tree_Node q2 = query(rt, 1+(a+b)/2, b, i, j);
if(q1.two==dummy.two) return q2;
if(q2.two==dummy.two) return q1;
Tree_Node res;
res.two = q1.two + q2.two;
res.five = q1.five + q2.five;
return res;
}
int main()
{
//freopen("zeros.in","r",stdin);
//freopen("zeros.out","w",stdout);
int i,n,q,x,l,r,c,t;
Tree_Node val,ans;
dummy.two=-1;
//Calculating the count of 2 and 5 in prime factorization of a no. for no.s upto 2000
for(i=2; i<=2000; i++)
{
x=i;
while(x%5==0)
{
div5[i]++;
x/=5;
}
while(!(x&1))
{
div2[i]++;
x/=2;
}
}
cin.sync_with_stdio(false);
cin.tie(NULL);
//scanf("%ld",&t);
cin>>t;
while(t--)
{
//scanf("%ld%ld",&n,&q); //Input n and q
cin>>n>>q;
for(i=0; i<n; i++)
{
//scanf("%ld",&x); // Input a[i]
cin>>x;
//Only the count of 2 and 5 in it's prime factorization is needed
arr[i].two=div2[x];
arr[i].five=div5[x];
}
build(1, 0, n-1); //Build segment tree
for(i=0; i<q; i++)
{
//scanf("%ld%ld%ld",&c,&l,&r);
cin>>c>>l>>r;
l--; //Decrease by 1 since array is 0-indexed
r--;
if(c==1)
{
ans=query(1, 0, n-1, l, r); //Query range [l, r] for total no. of twos and fives
printf("%ld\n",min(ans.two,ans.five));
}
else
{
//scanf("%ld",&x);
cin>>x;
val.two=div2[x]; //Only the count of 2 and 5 in it's prime factorization is needed
val.five=div5[x];
update(1, 0, n-1, l, r, val); // Increment range [l, r] by twos and fives of 'val'
}
}
}
return 0;
}
