Problem B. gCube - Google Code Jam 2016

https://code.google.com/codejam/contest/4284486/dashboard#s=p1

Googlers are very interested in cubes, but they are bored with normal three-dimensional cubes and also want to think about other kinds of cubes! A "D-dimensional cube" has D dimensions, all of equal length. (D may be any positive integer; for example, a 1-dimensional cube is a line segment, and a 2-dimensional cube is a square, and a 4-dimensional cube is a hypercube.) A "D-dimensional cuboid" has D dimensions, but they might not all have the same lengths.

Suppose we have an N-dimensional cuboid. The N dimensions are numbered in order (0, 1, 2, ..., N - 1), and each dimension has a certain length. We want to solve many subproblems of this type:

1. Take all consecutive dimensions between the L_i-th dimension and R_i-th dimension, inclusive.

2. Use those dimensions to form a D-dimensional cuboid, where D = R_i - L_i + 1. (For example, if L_i = 3 and R_i = 6, we would form a 4-dimensional cuboid using the 3rd, 4th, 5th, and 6th dimensions of our N-dimensional cuboid.)

3. Reshape it into a D-dimensional cube that has exactly the same volume as that D-dimensional cuboid, and find the edge length of that cube.

Each test case will have M subproblems like this, all of which use the same original N-dimensional cuboid.

Input

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case begins with two integers N and M; N is the number of dimensions and M is the number of queries. Then there is one line with N positive integers a_i, which are the lengths of the dimensions, in order. Then, M lines follow. In the ith line, there are two integers L_i and R_i, which give the range of dimensions to use for the ith subproblem.

Output

For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1). After that, output M lines, where the ith line has the edge length for the ith subproblem. An edge length will be considered correct if it is within an absolute error of 10^-6 of the correct answer. See the FAQ for an explanation of what that means, and what formats of real numbers we accept.

Limits

1 ≤ T ≤ 100.
1 ≤ a_i ≤ 10⁹.
0 ≤ L_i ≤ R_i < N.

Small dataset

1 ≤ N ≤ 10.
1 ≤ M ≤ 10.

Large dataset

1 ≤ N ≤ 1000.
1 ≤ M ≤ 100.

Sample

Input	Output
2 2 2 1 4 0 0 0 1 3 2 1 2 3 0 1 1 2	Case #1: 1.000000000 2.000000000 Case #2: 1.414213562 2.449489743

http://blog.yxbilu.com/blog/r/1440827351.html
http://www.lxway.com/852154641.htm
其实就是很l r区间的数乘积开根号就可以了。

int l = scanner.nextInt();

int r = scanner.nextInt();

int d = r - l + 1;

double multi = 1.0;

for (int k = l ; k <= r ; k++) {

      multi = multi * Math.pow(dim[k], 1.0/d);

}

http://blog.csdn.net/lwfcgz/article/details/47980749