Visit Counter
AmazingCounters.com

1、题目大意:定义g(x)为x的约数个数,如果对于任意的y使得y < x且 g(y) < g(x),那么x成为反质数
现在,让你求一个区间内的反质数区间的两个端点 <= 10^9
2、分析:不要看着区间很大就被吓唬住了,其实啊,这道题打表是可以AC的,因为总共也没有多少的反质数
但是因为我比较人性,所以没有打表,那么怎么做呢,对于dp一向很敏感的我把这题硬生生的写成的dp
我们看反质数的特点,是不是可以发现其实反质数分布很稀疏,我们可以求出当约数个数是x的时候,最小的数是多少
因为次小的,次次小的,都是不合法的,这样,我们就淘汰了一大半,只要我们求出这个,随便的搞搞就过了
怎么求呢》》》》》
我们由约数公式可以得到,我们要将x分解因数,然后对于所有的因数我们把对应的质数给它,然后根据约数公式还原
但是我们如果暴力的话会感觉要虚啊,于是动态规划大法好,,,,,,,,,
我们发现对应的质数我们只需要前25个就够了,于是小学被了前100的质数,然后我就手写的质数表233
我们根据约数公式来dp,我们从最后一位向前dp,然后一个一个玩,然后就AC了,,,,
3、代码:

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
LL prime[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 f[50][700];
LL ans[200000];
LL real_ans[200000];
pair<LL , LL> st[200000];
LL power(LL o, LL x, LL p){
    if(x == 0) return 1;
    if(x == 1) return o;
    LL k = power(o, x / 2, p);
    if(k > p || k == -1 || k * k > p) return -1;
    if(x & 1) return k * k * o;
    else return k * k;
}
int main(){
    LL n, m;
    scanf("%lld%lld", &n, &m);
    f[26][1] = 1;
    for(LL i = 25; i >= 1; i --){
        for(LL j = 1; j <= 600; j ++){
            f[i][j] = 200000000;
            for(LL k = 1; k <= sqrt(j); k ++){
                if(j % k == 0){
                    LL w = j / k;
                    LL t; 
                    if(f[i + 1][k] != 0){
                        t = power(prime[i], j / k - 1, m / f[i + 1][k]);
                        if(t != -1)   f[i][j] = min(f[i][j], f[i + 1][k] * t);
                    }
                    if(f[i + 1][w] != 0){
                        t = power(prime[i], j / w - 1, m / f[i + 1][w]);
                        if(t != -1) f[i][j] = min(f[i][j], f[i + 1][w] * t);   
                    }
                }
            }
            if(f[i][j] == 200000000) f[i][j] = 0;
        }
    }
    LL mm1 = 0, mm2 = 0;
    LL tot1 = 0, tot = 0;
    for(LL i = 1; i <= 600; i ++){
        if(f[1][i] != 0){
            st[++ tot].first = f[1][i];
            st[tot].second = i; 
        }
    }
    sort(st + 1, st + tot + 1);
    for(LL i = 1; i <= tot; i ++){
        if(st[i].first > mm1 && st[i].second > mm2){
            ans[++ tot1] = st[i].first;
            mm1 = st[i].first;
            mm2 = st[i].second;
        }
    }
    LL wt = 0;
    for(LL i = 1; i <= tot1; i ++){
        if(n <= ans[i] && ans[i] <= m) real_ans[++ wt] = ans[i];
    }
    if(wt == 0){
        printf("NO");
        return 0;
    }
    for(LL i = 1; i < wt; i ++) printf("%lld,", real_ans[i]);
    printf("%lld", real_ans[wt]);
    return 0;
}