Influence on Social media(素论+思维)

传送门：nefu_10-18 - Virtual Judge (vjudge.net)

思路：

每次给n个数，判断每个数的除数总数是否为奇素数。

对于整数：可质因子分解， $p1^{i1}*p2^{i2}*p3^{i3}.....$ ,除数总数为（i1+1）*(i2+1)*(i3+1)....

若除数总数为奇素数，则（i1+1）*(i2+1)*(i3+1)....最多只有一项（有多项显然不是素数），并且i+1为奇素数，易知素数除2外都为奇数，所以i+1>=3,i>=2;

i>=2,则Pi<=1e6;

我们可以预处理：

我们先用素数筛筛出1-1e6素数，然后枚举每个素数xi（x1>=2）；

对于每个素数xi,我们找出所有满足条件的答案；

可以枚举xi的次数，i:2-60（因为最小素数2^60>1e12,60次方足够），当i+1为素数时，满足条件，记录下来。

代码：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<unordered_map>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 1e6+100;
unordered_map<LL, int> p;
int a[N],su[N],cnt;
LL s[N/10];
void into()
{
   a[0] = a[1] = 1;
   for (int i = 2; i <= N; i++)
   {
       if (!a[i])
           su[++cnt] = i;
       for (int j = 1; su[j] <= N / i; j++)
       {
           a[su[j] * i] = 1;
           if (i % su[j] == 0) break;
       }
   }

}
void into2()
{
   for (int i = 1; i <= cnt; i++)
   {
       LL x = su[i];
       for (int j = 2; j <= 64; j++)
       {
           x *= su[i];
           if (!a[j + 1])
               p[x] = 1;
           if (x > 1e12) break;
       }
}
}
bool cmp(LL c, LL d)
{
   return c > d;
}
int main() {
   into();
   into2();
   int T;
   cin >> T;
   while (T--)
   {
       int n,flag=0;
       scanf("%d", &n);
       for (int i = 1; i <= n; i++)
           scanf("%lld", &s[i]);
       sort(s + 1, s + 1 + n, cmp);
       for (int i = 1; i <= n; i++)
       {
           if (p[s[i]])
               printf("%d ", i),flag=1;
       }
       if (!flag)
           printf("No supporter found.");
       printf("\n");
   }
   return 0;
}