Count the Co Prime Number

Alamin_just Ada Lovelace National Gir...
Limits 1s, 512 MB

Wow, The statement is very clear, you are given an array AA that contains NN number of positive integers and another array BB and BB also contains NN positive integers. Initially all the elements of BB are zero. You have three types of queries. The queries are:

1 l r s ( you have to update l to r like this B[l]=A[s],B[l+1]=A[s+1],B[l+2]=A[s+2]B[l] = A[s], B[l+1] = A[s+1], B[l+2] = A[s+2]… and so on ).

2 l r s ( you have to update r to l like this B[r]=A[s],B[r1]=A[s1],B[r2]=A[s2]...B[r] = A[s], B[r-1] = A[s-1], B[r-2] = A[s-2]... and so on ).

3 u v ( you have to give the answer. Find how many numbers exist such that GCD(R,L)=1GCD(R, L) = 1).

Suppose R=B[u]B[v]R = B[u] * B[v] and ( R>=L>=0R >= L >= 0 )

Input

The first line of contains N(1N100000)N( 1 \le N \le 100000)- number of elements in array AA

Next NNlines contain A1,A2,A3...,AN(1Ai1000000)A_1, A_2, A_3..., A_N (1 \le A_i \le 1000000)

Next line contains a positive integer Q(1Q100000)Q (1 \le Q \le 100000)- the number of queries.

Next QQlines contain the queries in the format given below.

First number of each of these line contains the query type 11 or 22 or 33.

In case of query type 11or 22, the next three numbers will be l,r,s.l, r, s.(1<=l<=r<=n)( 1 <= l <= r <= n )

for the query type 11(1<=s<=n(rl))( 1 <= s <= n-(r-l) )and for the query type 22 (1+(rl)<=s<=n)( 1 + ( r - l ) <= s <= n )

In case of query type 3, the next two numbers will be u,vu, v. (1<=u<=v<=n)( 1 <= u <= v <= n )

See the sample test for a better understanding.

Output

For each of the query type 33 you have to print the answer to the query in separate lines.

Sample

InputOutput
4
2
3
4
6
4
1 2 3 1
2 2 4 3
3 2 4
3 1 1
4
0

Explanation:

Explanation of the 11'st case.

Initially: BB== { 0,0,0,00 , 0 , 0 , 0 }

After the 11st query: BB== { 0 , 2 , 3 , 0 }

After the 22nd query: B == { 0,2,3,40 , 2 , 3 , 4 }

B[2]=2B[2] = 2, B[4]=4B[4] = 4

So R=8R = 8.

L=[0,1,2,3,4,5,6,7,8]L = [ 0, 1, 2, 3, 4, 5, 6, 7, 8 ]

GCD(1,8)=GCD(3,8)=GCD(5,8)=GCD(7,8)=1GCD(1,8) = GCD(3,8) = GCD(5,8) = GCD(7,8) = 1

So the answer is 44

Submit

Login to submit.

Statistics

64% Solution Ratio
Rawaha0909Earliest, 2M ago
steinumFastest, 0.0s
steinumLightest, 8.9 kB
steinumShortest, 1411B
Toph uses cookies. By continuing you agree to our Cookie Policy.