18710번 - Greatest Chicken Dish 다국어

Fouad, the ACPC judges, and organizers were hungry, so they went to a restaurant. This restaurant makes chicken cubes in seekh (skewers), such that each seekh has N chicken cubes in which the i^th cube has an integer A_i that represents the mixture of spices used to cook that cube. A set of successive cubes are considered delicious from Fouad’s perspective when the greatest common divisor (GCD) of their mixture of spices is exactly equal to D.

Since Fouad wants to try many sub-parts of the seekh, he keeps asking the judges some queries such that each query consists of three integers L, R, and D, and he wants to know what is the number of consecutive sub-parts of the seekh in the range A_L, A_L+1, · · · , A_R that the GCD of their mixtures of spices is equal to D; that is the count of all pairs (i, j) such that gcd(A_i, A_i+1, · · · , A_j) = D and L ≤ i ≤ j ≤ R.

Since the judges want to relax and not solve problems and just eat, they asked you to solve this problem for them. Can you solve it?

The first line of the input contains a single integer T specifying the number of test cases.

Each test case begins with a line containing two integers N and Q (1 ≤ N ≤ 10⁵, 1 ≤ Q ≤ 5 · 10⁴), in which N is the number of chicken cubes in a seekh, and Q is the number of queries Fouad will ask.

Then a line follows containing N integers A₁, · · · , A_N (1 ≤ A_i ≤ 10⁶), in which Ai represents the mixture of spices used to cook the i^th chicken cube.

Then Q lines follow, each line contains three space-separated integers L, R, and D (1 ≤ L ≤ R ≤ N, 1 ≤ D ≤ 10⁶), giving the queries.

For each test case, print a single line per query containing the number of consecutive sub-parts of the seekh in the given range [L, R] that the GCD of their mixtures of spices is equal to D.

Greatest Common Divisors of multiple arguments is computed recursively according to the equation gcd(x₁, x₂, · · · , x_n) = gcd(gcd(x₁, · · · , x_n−1), x_n).