C题解 【LittleXi】头好痛感觉要长脑子了O.o?

玄学题，时间复杂度O(能过)
其实仔细算一下时间复杂度不超过O(ans+n)

解题思路

其实出题人已经疯狂暗示了这个题的解法
保证输出的num数量不会超过9e7，并且说了两次这个
那么其实我们想要的cnt大概率就是一个一个数
那么怎么数呢？

题目说了这n个数每个数的平方的约数只有3个 , 其实就是质数

好，那我们统计的时候，直接暴力dfs，先排序然后简单剪枝一下，就可以通过啦

注意会爆long long~

运行时间500ms

//哔哩哔哩求关注qwq:https://space.bilibili.com/524432272?spm_id_from=333.1007.0.0
#include<bits/stdc++.h>
using namespace std;
#define int long long

vector<int> a;
int r = 0 ,cnt = 0;
void dfs(int i, int val)
{
    if (val <= r && val > 1)
        cnt++;
    for (int j = i; j < a.size(); j++)
    {
        __int128 t = (__int128)val * (__int128)a[j];
        if (t > (__int128)r)  break;
        dfs(j, val * a[j]);
    }
}

void solve()
{
    int n;
    cin>>n;
    a.resize(n);
    for(int&x:a)cin>>x;
  	a.erase(unique(a.begin(),a.end()), a.end());
    sort(a.begin(), a.end());
    cin>>r;
    dfs(0, 1);
    cout << cnt << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
}