反素数

做一道线段树的题目看到了反素数的概念，然后就去看了一下，线段树倒是没做出来，学习了一下反素数

首先给出定义：对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数.

反素数的两条性质：1.一个反素数的质因子必然是从2开始连续的质数. 2:p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=....

View Code

 1 // 求解反素数的过程
 2 
 3 // num：当前枚举到的数
 4 // k：枚举到的第k大的质因子
 5 // sum：该数的约数个数
 6 // limit：质因子个数上限
 7 void getantiprime(ll num,ll k,ll sum,int limit)
 8 {
 9     int i;
10     ll temp;
11     if(sum > maxsum)  // 如果约数个数更多，将最优解更新
12     {
13         maxsum = sum;
14         bestnum = num;
15     }
16     if(sum == maxsum && bestnum > num)  // 如果约数个数相同，将最优解更新为较小的数
17     bestnum = num;
18     if(k > 15)
19     return ;
20     temp = num;
21     for(i = 1; i <= limit; i++)  // 枚举每个质因子
22     {
23         if(temp * prime[k] > n) break;
24         temp = temp * prime[k];  // 累乘到当前数
25         getantiprime(temp,k + 1,sum * (i + 1),i);  // 继续下一步的搜索
26     }
27 }

下面就是一个裸的求 1 到 n 范围内的反素数题目 http://acm.hdu.edu.cn/diy/contest_showproblem.php?cid=16253&pid=1004

但是做的时候完全不知道这是在求反素数，竟然打表，然后果断的MLE了，

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 
 7 typedef long long ll;
 8 const int prime[16]= {1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
 9 ll maxsum,bestnum,n;
10 void getantiprime(ll num,ll k,ll sum,int limit)
11 {
12     int i;
13     ll temp;
14     if(sum > maxsum)
15     {
16         maxsum = sum;
17         bestnum = num;
18     }
19     if(sum == maxsum && bestnum > num)
20     bestnum = num;
21     if(k > 15)
22     return ;
23     temp = num;
24     for(i = 1; i <= limit; i++)
25     {
26         if(temp * prime[k] > n) break;
27         temp = temp * prime[k];
28         getantiprime(temp,k + 1,sum * (i + 1),i);
29     }
30 }
31 int main()
32 {
33     int t;
34     //freopen("data.txt","r",stdin);
35     scanf("%d",&t);
36     while(t--)
37     {
38         scanf("%lld",&n);
39         getantiprime(1,1,1,50);
40         printf("%lld\n",bestnum);
41     }
42     return 0;
43 }