一、题目内容

题目描述

黑妹又开始玩起了一个游戏，这次她面对的是一个序列，序列里的每个数字都是正整数，黑妹每次可以从这个序列里选择两个数字，然后将这两个数字除以它们任意一个公共因子。
如果 x 是 a 和 b 的公共因子，当且仅当 a 和 b 都能被 x 整除。
黑妹很快玩腻了这些操作，她现在想知道，这个序列经过一些操作之后，将新序列的每个元素都乘起来的最小乘积是多少，由于这个乘积可能很大，所以你需要告诉黑妹这个乘积对10⁹+7取模之后的值。

输入描述

第一行一个整数T表示数据的组数。(1 ≤ T ≤ 10)
对于每组数据：
第一行n表示序列的长度。(1 ≤ n ≤ 10000)
接下来一行n个整数ai表示序列的每个元素。(1 ≤ ai ≤ 10⁸)

输出描述

对于每组数据输出一行表示答案。

示例1

输入

3
3
1 2 3
4
8 8 9 9
5
4 8 12 18 22

输出

6
1
66

二、解题思路

题中：x为a、b的公共因子，且a、b都能被x整除，很明显是枚举素因子（prime），对于a：1 <= a <= 10⁸,对于a来说大于10⁴的素因子最多就一个，因此我们只需要枚举初10⁴以内的质因数即可。那么问题来了，枚举质因数后如何确定可以消去多少个？

我们可以对每个素因子单独考虑，假设素因子p在a₁，...，a_n中的幂指数分别为：b₁，...，b_n，不妨假设b₁ <= b₂ <= ... <= b_n，显然只要 $2 * b_n \leq \sum^{n}_{i = 1}{b_i}$ ，这些幂指数就可以成对消除，最后剩余 $\sum^{n}_{i = 1}{b_i}$ % $2$ 个p，否则只能用 $b_1，...，b_{n-1}去消除b_n，最后剩余2 * b_n - \sum^{n}_{i = 1}b_i个p$ ，以此考虑每个素因子，即可取的答案。

代码实操

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
#define mem(a, b) memset(a, b, sizeof(a))
#define lson (root << 1)
#define rson (root << 1 | 1)

const int N = 1e4 + 100;
const int mod = 1e9 + 7;

bool vis[N];
int prime[N],t;
map<int, int>mp;
void init() {
    for(int i = 2; i < N; i++) {
        if (!vis[i]) {
            prime[t++] = i;
            for(int j = 2 * i; j < N; j += i) {
                vis[j] = 1;
            }
        }
    }
}

vector<int>dat[N];

void process(int x) {
    for(int i = 0; prime[i] * prime[i] <= x;i++) {
        if (x % prime[i] == 0) {
            int cnt = 0;
            while(x % prime[i] == 0) {
                cnt++;
                x /= prime[i];
            }
            dat[prime[i]].push_back(cnt);
        }
    }
    if (x != 1) {
        if (x < N) {
            dat[x].push_back(1);
        } else {
            mp[x]++;
        }
    }
}

priority_queue<int>que;
ll solve(vector<int>& ve, int x) {
    if (!ve.size()) return 1LL;
    while(!que.empty()) que.pop();
    for(int i = 0; i < (int)ve.size(); i++) {
        que.push(ve[i]);
    }
    while(que.size() >= 2) {
        int u = que.top();
        que.pop();
        int v = que.top();
        que.pop();
        u--,v--;
        if (u >= 1) que.push(u);
        if (v >= 1) que.push(v);
    }
    int cnt = 0;
    if (!que.empty()) cnt = que.top();
    
    ll ans = 1;
    while(cnt--) ans *= x;
    return ans;
}

int a[N];
void solve() {
    int n;
    cin >> n;
    mp.clear();
    for(int i = 0; i < N; i++) {
        dat[i].clear();
    }
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        process(a[i]);
    }
    ll ans = 1;
    for(int i = 0; i < t; i++) {
        if (!dat[prime[i]].size()) continue;
        ans *= solve(dat[prime[i]],prime[i]);
        ans %= mod;
    }
    for(map<int,int>::iterator it = mp.begin(); it != mp.end(); it++) {
        if (it -> second % 2) {
            ans = ans * it -> first % mod;
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    init();
    int T;
    cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

最后编辑于：2019.12.04 16:22:47