题解 P1463 【[POI2002][HAOI2007]反素数】

· · 题解

看了看好像都是打表的

我来说一说正解吧

1、分析题意

性质1： 划重点、敲黑板
1~N中的最大的反质数，就是1~N中约数个数最多的数中最小的一个 。

简证：
设m是1~N中约数个数最多的数中最小的一个。根据m的定义，m显然满足：
第一条性质：

{\forall}x < m, g(x) < g(m)

第二条性质：

{\forall} x > m , g(x) ≤ g(m)

根据反素数的定义，第一条性质说明 m 是反质数，第二条性质说明大于 m 的数都不是反质数，所以 m 即为所求。

性质2： 再敲黑板
1~N中任何的不同质因子都不会超过10个，且所有质因子的指数总和不超过30。

简证：这个很好证明 qwq
最小的 11 个质数的积
2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 ＞ 2 * 10^9
所以，N ≤ 2 10^9 不可能有多于10个不同的质因子。
即使只包含最小的质数2，仍然有 2 ^ 31 ＞ 2 10^9 所以 N ≤ 2 * 10^9 的质因子不会超过30个。

性质3： 累了，不敲了

{\forall}x ∈ [1,N]

x为反质数的必要条件是：x分解质因数后可写作2^c1 3^c2 ...... *29 ^ c10，并且c1≥c2≥c3≥......≥c10≥0 。
通俗的讲，x的质因子是连续的若干个最小的质数，并且质数单调递增。

简证： 采用反证法。由性质2可得，若x的质因数分解式中存在一项p^k（p>29），则必定有一个不超过29的质因子p1不能整除x。根据算数基本定理的推论，x / p^k * p1^k 的约数个数与x的约数个数相等，但前者更小，这与反质数的定义矛盾。故x只包含29以内的质因子。
同理，若x的质因子不是连续的若干个最小的，或者指数不单调递减，我们也可以通过上述交换质因子的方法，得到一个比x更小、但约数个数相等的整数。因此，假设不成立，原命题成立。

综上所述，我们可以使用DFS尝试搜索前10个质数的指数，并满足指数递减、总乘积不超过N，同时记录约数的个数。
在这两个限制条件下，搜索量实际非常小，每当搜索出一个满足条件的整数的时候，我们就按照性质一的结论更新答案，最终得到约数个数最多的数中最小的一个。

按理来说应该到了撒花结尾的时刻了，但是我还是打算放上代码 

#include <algorithm>
#include <iostream>
#include <cstdio>
#define ll long long

using namespace std ;

int pri[15] = {0,2,3,5,7,11,13,17,19,23,29,31};
//最小的11个质数 
ll best = -1 , num = -1 ;
//万一答案是0呢？ 
int n ;

void dfs(ll x  , int rest , int m, int up)
//x为当前数字的大小，m为当前数字约数的个数
//rest为当前质数的编号，up为小于三十的当前指数和
{
    if(m > best || (m == best && x < num))
        num = x , best = m ;
        //根据性质一的更新答案过程 
    ll ans = x ;
    int i = 0 ;
    while(i < up)
    {
        ++ i ;
        if(n / ans < pri[rest]) 
        //保证总乘积不超过N 
            return ;
        int kkk = m * (i + 1 ) ;
        ans *= pri[rest] ;
        if(ans <= n)
            dfs(ans , rest + 1 , kkk , i) ;
            //保证了质数的单调递减 
    }
    //加上这两个搜索的剪枝，就会感到dfs快的飞起  哈哈哈 
}

int main()
//及其卑微的主函数 
{
    scanf("%d" , &n) ;
    dfs(1 , 1 , 1 , 30);
    printf("%lld\n" , num);
}

看懂再抄谢谢