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
Input
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.
Output
For each test case, output a single line containing the first term of the sequence which is the perfect cube, modulo 109+7.
Constraints
- 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.
Example
Input:
2
2
2 2
2
2 3
Output:
8
216
Explanation
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).
【分析】
挺模板的东西，就当复习一下了。
/*
宋代李冠
《蝶恋花·春暮》
遥夜亭皋闲信步。
才过清明，渐觉伤春暮。
数点雨声风约住。朦胧淡月云来去。
桃杏依稀香暗渡。
谁在秋千，笑里轻轻语。
一寸相思千万绪。人间没个安排处。
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <iostream>
#include <string>
#include <ctime>
#include <map>
#define LOCAL
const int MAXN = + ;
const long long MOD = ;
const double Pi = acos(-1.0);
long long G = ;//原根
const int MAXM = * + ;
using namespace std;
typedef long long ll;
ll read(){
ll flag = , x = ;
char ch;
ch = getchar();
while (ch < '' || ch > '') {if (ch == '-') flag = -; ch = getchar();}
while (ch >= '' && ch <= '') {x = x * + (ch - ''); ch = getchar();}
return x * flag;
}
map<ll, int>Num;//记录个数
ll data[MAXN];
ll n; ll mul(ll a, ll b, ll c){//又要用快速乘QAQ
if (b == ) return 0ll;
if (b == ) return a % c;
ll tmp = mul(a, b / , c);
if (b % == ) return (tmp + tmp) % c;
else return (((tmp + tmp) % c) + (a % c)) % c;
}
ll pow(ll a, ll b, ll c){
if (b == ) return 1ll;
if (b == ) return a % c;
ll tmp = pow(a, b / , c);
if (b % == ) return mul(tmp, tmp, c);
else return mul(mul(tmp, tmp, c), a, c);
}
bool Sec_check(ll a, ll b, ll c){
ll tmp = pow(a, b, c);
if (tmp != && tmp != (c - )) return ;
if (tmp == (c - ) || (b % != )) return ;
return Sec_check(a, b / , c);
}
//判断n是否是素数
bool miller_rabin(ll n){
int cnt = ;
while (cnt--){
ll a = (ll)rand() % (n - ) + ;
if (!Sec_check(a, n - , n)) return ;
}
return ;
}
ll gcd(ll a, ll b){return b == 0ll ? a : gcd(b, a % b);}
ll pollard_rho(ll a, ll c){
ll i = , k = ;
ll x, y, d;
x = (ll)((double)(rand() / RAND_MAX) * (a - ) + 0.5) + 1ll;
y = x;
while (){
i++;
x = (mul(x, x, a) % a + c) % a;
d = gcd(y - x + a, a);
if (d > && d < a) return d;
if (y == x) return a;//失败
if (i == k){
k <<= ;
y = x;
}
}
}
void find(ll a, ll c){
if (a == ) return;
if (miller_rabin(a)){
Num[a]++;
return;
}
ll p = a;
while (p >= a) pollard_rho(a, c--);
pollard_rho(p, c);
pollard_rho(a / p, c);
}
void init(){
Num.clear();
scanf("%d", &n);
for (int i = ; i <= n; i++) {
data[i] = read();
find(data[i], );
}
}
void work(){
ll Ans = ;
for (int i = ; i <= n; i++) Ans = (Ans * data[i]) % MOD;
for (map<ll, int>::iterator it = Num.begin(); it != Num.end(); it++){
it->second %= ;
if (it->second){
for (int i = it->second; i < ; i++) Ans = (Ans * ((it->first) % MOD)) % MOD;
}
}
printf("%lld\n", Ans);
} int main(){
int T; scanf("%d", &T);
while (T--){
init();
work();
}
return ;
}