在社交媒体中，用户通过发布内容表达观点。假设一个群体中有 N 个人，每个人发布的帖子数量决定了其影响力。然而，判断一个人是否支持某项政策并非易事，因为他们的帖子可能包含模糊的暗示和无关的讨论。幸运的是，Facebook AI 团队发现了一种规律：如果一个人发布的帖子数量的因子个数是一个奇素数，则这个人是支持者。

问题描述

给定一组人发布的帖子数量 Pi（每人不同），我们需要找出所有支持者，并按其总体影响力排名输出。具体来说，对于每个支持者，我们需要找到他们在整个群体中的影响力排名（即按帖子数量降序排列后的序号）。

输入格式

第一行包含一个整数 T，表示测试用例的数量。接下来 T 组测试数据：

• 每组测试数据的第一行为一个整数 N，表示人数。
• 第二行为 N 个空格分隔的整数，表示每个人的帖子数量 Pi。

输出格式

对于每组测试数据，输出一行结果：

• 如果存在支持者，按照从高到低的影响力顺序输出他们的排名。
• 如果没有支持者，输出 "No supporter found."。

示例

<strong>输入:</strong>
2
2
1 3
2
13 9

<strong>输出:</strong>
No supporter found. 
2

解释

示例 1：第一个人发布了 1 条帖子，其因子个数为 1（非素数），因此不是支持者；第二个人发布了 3 条帖子，因子个数为 2（偶数），也不是支持者。因此输出 "No supporter found."。

示例 2：第一个人发布了 13 条帖子，因子个数为 2（偶数），不是支持者；第二个人发布了 9 条帖子，因子个数为 3（奇素数），是支持者。其在整体排序中位于第 2 名，因此输出 2。

---

算法思路

1. 质因数分解：根据公式 ( N = p_1^{c_1} \times p_2^{c_2} \times ... \times p_k^{c_k} )，因子个数为 ((c_1 + 1) \times (c_2 + 1) \times ... \times (c_k + 1))。要使因子个数为奇素数，必须满足以下条件：

• ( N = p_1^{c_1} )，即 ( N ) 只能由单一质数的幂构成。
• ( c_1 + 1 ) 是一个素数。

2. 预处理：使用埃拉托色尼筛法生成一定范围内的素数，并计算这些素数的幂次，直到超过 ( 10^{12} )。

3. 快速查找：将所有符合条件的 ( N ) 存入哈希表，以便快速判断某个数字是否为支持者的帖子数量。

4. 排序与输出：对所有帖子数量按降序排序，逐一检查是否为支持者，并记录其排名。

---

实现代码

以下是优化后的 C++ 实现代码：

#include <bits/stdc++.h>
using namespace std;

const long long MAX_P = 1e6 + 5;
vector<long long> primes;
unordered_map<long long, bool> validNumbers;

// 素数筛选
void sieve() {
    vector<bool> isPrime(MAX_P, true);
    isPrime[0] = isPrime[1] = false;
    for (long long i = 2; i < MAX_P; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (long long j = i * i; j < MAX_P; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

// 预处理所有符合条件的数字
void preprocess() {
    for (auto p : primes) {
        long long num = p;
        for (int exp = 2; exp <= 60; ++exp) {
            num *= p;
            if (num > 1e12) break;
            if (isprime(exp)) { // 判断指数加一是否为素数
                validNumbers[num] = true;
            }
        }
    }
}

// 判断是否为素数
bool isprime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    sieve(); // 初始化素数列表
    preprocess(); // 预处理符合条件的数字

    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<long long> posts(N);
        for (int i = 0; i < N; ++i) {
            cin >> posts[i];
        }

        // 按帖子数量降序排序
        sort(posts.begin(), posts.end(), [&](const long long &a, const long long &b) -> bool {
            return a > b;
        });

        vector<int> supporters;
        for (int i = 0; i < N; ++i) {
            if (validNumbers[posts[i]]) {
                supporters.push_back(i + 1); // 记录排名
            }
        }

        if (supporters.empty()) {
            cout << "No supporter found.\n";
        } else {
            for (int i = 0; i < supporters.size(); ++i) {
                cout << supporters[i] << (i == supporters.size() - 1 ? '\n' : ' ');
            }
        }
    }
    return 0;
}