The First Cube
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
This problem's statement is really a short one.
You are given an integer S. Consider an infinite sequence S, 2S, 3S, ... . Find the first number in this sequence that can be represented as Q3, where Q is some positive integer number. As the sought number could be very large, please print modulo (109 + 7).
The number S will be given to you as a product of N positive integer numbers A1, A2, ..., AN, namely S = A1 * A2 * ... * AN
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains an integer N.
Then there is a line, containing N space separated integers, denoting the numbers A1, A2, ..., AN.
For each test case, output a single line containing the first term of the sequence which is the perfect cube, modulo 109+7.
- 1 ≤ T ≤ 10
- (Subtask 1): N = 1, 1 ≤ S ≤ 109 - 15 points.
- (Subtask 2): N = 1, 1 ≤ S ≤ 1018 - 31 point.
- (Subtask 3): 1 ≤ N ≤ 100, 1 ≤ Ai ≤ 1018 - 54 points.
Input: 2 2 2 2 2 2 3 Output: 8 216
Example case 1. First few numbers in the infinite sequence 4, 8, 12, 16, 20, , etc. In this sequence, 8 is the first number which is also a cube (as 23 = 8).
Example case 2. First few numbers in the infinite sequence 6, 12, 18, 24, , etc. In this sequence, 216 is the first number which is also a cube (as 63 = 216).
|Tags||ltime21, medium, prime, xcwgf666|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.