Influence on Social media(素论+思维)

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

思路：

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

对于整数：可质因子分解，,除数总数为（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
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

}
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;
}