gCube

The question is equal to given a series of large value and give a range. You are asked to multiply all these range and as to get the high dimension D cube's edge length, we have to get it's Dth root.

There are two key point in this question: the calculation of nth root with high precision and calculation the multiplication of a large number which even exceeds the range of double type.

To calculate the nth root of a number num, other than implementing our own newton's method, a more convenient way might be using a formular $\sqrt[n]{num} = num^{\frac{1}{n}}$ so that we can calculate by something like Math.pow(num, 1/n). But directly calculate some number's $\frac{1}{n}$th power works bad if n is very big. An alternative is applying $num^{\frac{1}{n}} = e^{\frac{\ln{num}}{n}}$. That will satisfied the precision requirements.

As for the second problem, actually we are not required to calculate the muliplication of all those numbers, we are asked to calculate $\sqrt[n]{A_1, A_2, \cdots, A_n}$. It is equals to that we calculate the nth root first before multiplying them. That is:

$$\sqrt[n]{A_1\cdot A_2\cdots A_n} = \sqrt[n]{A_1}\cdot \sqrt[n]{A_2}\cdots \sqrt[n]{A_n}$$

So that we can get the result without calculate a multiplication that exceeds range without losing precision. One should keep this method in mind as many times we will need to do similar formular transformation to enable big number calculation without using something like BigDecimal.

import java.io.*;
import java.util.*;

public class GCube {
    public static double root(double num, double root) {
        return Math.pow(Math.E, Math.log(num)/root);
    } 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int t = 0; t < T; t++) {
            int N = in.nextInt(), M = in.nextInt();
            double[] dimension = new double[N];
            for (int i = 0; i < N; i++) {
                dimension[i] = in.nextDouble();
            }
            System.out.printf("Case #%d:\n", t + 1);
            for (int j = 0; j < M; j++) {
                int l = in.nextInt(), r = in.nextInt();
                double v = 1.0;
                for (int i = l; i <= r; i++) {
                    v *= root(dimension[i], r - l + 1);
                }
                System.out.printf("%.9f\n", v);
            }
        }
    }
}