题解 P1574 【超级数】

· · 题解

题目中的超级数跟反素数的定义是一样的

反素数就是尽可能地让因子数量最大，但是数值最小。

性质一:一个反素数的质因子必然是从2开始连续的质数.

性质二:p= (2^t1)(3^t2)(5^t3)(7^t4)..... 必然t1>=t2>=t3>=....

但是似乎没有人发生成反素数表的代码呢……

蒟蒻决定凑个热闹发一个生成反素数表的代码

根据数据范围，我们很容易想到暴力+打表

根据反素数的两条性质枚举，求出含有i个因数的最小正整数

所以我们先要打出一张质数表 代码如下：

#include<iostream>
#include<fstream>
using namespace std;
bool isprime(int x)
{
    if (x<2)
        return false;
    for (int i=2; i*i<=x; i++)
        if (x%i==0)
            return false;
    return true;
}
int main()
{
    freopen("prime.txt","w",stdout);
    int a=0;
    for (int i=1;i<=100;i++)
    {
        if (isprime(i))
        {
            cout<<i<<",";
            a++;
        }
        if (a==5)
        {
            cout<<endl;
            a=0;
        }
    }
    return 0;
}
/*
1:2
2:6
3:30
4:210
5:2310
6:30030
7:510510
8:9699690
9:223092870
10:6469693230
11:200560490130
12:7420738134810
13:304250263527210
14:13 08276 13316 70030
*/

将这些质数乘起来，显而易见在题目数据范围内，只需要用到前13个质数

于是我们用暴搜打出反素数表 代码如下：

#include<iostream>
#include<cstring>
#include<fstream>
#define ll long long
#define mmax 0x3f3f3f3f3f3f3f3f
using namespace std;
ll p[26]=
{
    0,
    2,3,5,7,11,
    13,17,19,23,29,
    31,37,41,43,47,
    53,59,61,67,71,
    73,79,83,89,97
};
ll ap[100001];
void dfs (ll n,ll y,ll t,ll x)
{
    if (n>=14)
        return;
    ll k=t;
    for (ll i=1; i<=x; i++)
    {
        k*=p[n];
        if (k>1e17)
            break;
        int ys=y*(i+1);
        if (k<ap[ys])
            ap[ys]=k;
        dfs(n+1,ys,k,i);
    }
}
int main()
{
    freopen("antiprime.txt","w",stdout);
    int hh=0;
    memset(ap,0x3f,sizeof(ap));
    ap[0]=0,ap[1]=1;
    dfs(1,1,1,60);
    for (int i=0; i<=100000; i++)
        if(ap[i]!=mmax)
        {
            int flag=0;
            for (int j=i; j<=100000; j++)
                if (ap[i]>ap[j])
                {
                    flag=1;
                    break;
                }
            if (!flag)
            {
                hh++;
                cout<<ap[i]<<",";
            }
            if (hh==5)
            {
                cout<<endl;
                hh=0;
            }
        }
    return 0;
}

打出反素数表之后就很容易ac了，但是要注意读入是用long long，不然就只有70分了

十年 OI 一场空，不开 long long 见祖宗

由于是打表，题目中的询问次数不超过十万次，而数据范围内的反素数并不多，所以连二分查找都不需要就能轻松ac

ac代码就不附了，毕竟可以看其他大佬的题解QwQ