题解|[HAOI2007]反素数ANT

因为前 $10$ 个素数乘积大于 $2e9$ , $2^31$ 也大于 $2e9$ 。所以反素数分解质因数后一定是在前 $10$ 个素数，而且指数不超过 $31$ .一定在前 $10$ 个素数。
证明：如果有一个反素数质因数 $p$ 不在这 $10$ 个素数，那么一定有一个这 $10$ 个素数内的 $p'$ 没有被用到，那么我们可以把这个反素数改一下(设为n),变成 $n/(p^c_i)*(p'^c_i)$ ，那么这样约数个数相同，但是变完后这个数更小，不符合反素数的定义，所以这个数一定不是反素数，所以反素数分解质因数后一定是在前10个素数里面。
而且必须是指数不升的，这个根据前面那个交换指数也可以证明。
所以只需要搜索前10个素数的指数，然后判定即可，有前面三个判定条件以及它不能超过n，实际搜索量非常小。

#include <bits/stdc++.h>

#define ll long long
#define inf 0x3f3f3f3f
#define il inline

namespace io {

    #define in(a) a=read()
    #define out(a) write(a)
    #define outn(a) out(a),putchar('\n')

    #define I_int ll
    inline I_int read() {
        I_int x = 0 , f = 1 ; char c = getchar() ;
        while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
        while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
        return x * f ;
    }
    char F[ 200 ] ;
    inline void write( I_int x ) {
        if( x == 0 ) { putchar( '0' ) ; return ; }
        I_int tmp = x > 0 ? x : -x ;
        if( x < 0 ) putchar( '-' ) ;
        int cnt = 0 ;
        while( tmp > 0 ) {
            F[ cnt ++ ] = tmp % 10 + '0' ;
            tmp /= 10 ;
        }
        while( cnt > 0 ) putchar( F[ -- cnt ] ) ;
    }
    #undef I_int

}
using namespace io ;

using namespace std ;

#define N 100010
ll p[11] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int id, n = read();
ll ans;

ll power(ll a, int b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a;
        a *= a; b >>= 1;
    }
    return ans;
}

void dfs(int x, int limit, ll sum, ll tot) {
    if(sum > n || sum <= 0) return;
    if(x == 11) {
        if(tot > id) {
            ans = sum;
            id = tot;
        } else if(tot == id) ans = min(ans, sum);
        return;
    }
    for(int j = limit; j >= 0; --j) {
        dfs(x + 1, j, 1ll * sum * power(p[x], j), 1ll * tot * (j + 1));
    }
}

int main() {
    dfs(1, 31, 1, 1);
    printf("%lld\n", ans);
}