反素数
问题描述:
对于任何正整数x,起约数的个数记做g(x).例如g(1)=1,g(6)=4.
定义：如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数.
现在给一个N,求出不超过N的最大的反素数.
比如:输入1000 输出 840
思维过程:
求[1..N]中最大的反素数–>求约数最多的数
如果求约数的个数 756=2^2*3^3*7^1
(2+1)*(3+1)*(1+1)=24
基于上述结论,给出算法:按照质因数大小递增顺序搜索每一个质因子,枚举每一个质因子
为了剪枝:
性质一:一个反素数的质因子必然是从2开始连续的质数.
因为最多只需要10个素数构造:2,3,5,7,11,13,17,19,23,29
性质二:p=2^t1*3^t2*5^t3*7^t4…..必然t1>=t2>=t3>=….
1 |
View Code |
2 |
typedef __int64 INT; |
3 |
INT bestNum; //约数最多的数 |
4 |
INT bestSum; //约数最多的数的约数个数 |
5 |
const int M=1000; //反素数的个数 |
6 |
INT n=500000;//求n以内的所有的反素数 |
7 |
INT rprim[M][2]; |
8 |
//2*3*5*7*11*13*17>n，所以只需考虑到17即可 |
9 |
INT prim[14]={2,3,5,7,11,13,17,19,23,29}; |
10 |
|
11 |
//当前走到num这个数，接着用第k个素数，num的约数个数为sum， |
12 |
//第k个素数的个数上限为limit |
13 |
void getNum(INT num,INT k,INT sum,INT limit) { |
14 |
if(num>n)return; |
15 |
if(sum>bestSum){ |
16 |
bestSum = sum; |
17 |
bestNum = num; |
18 |
}else if(sum == bestSum && num < bestNum){ //约数个数一样时，取小数 |
19 |
bestNum = num; |
20 |
} |
21 |
if(k>=7) return; //只需考虑到素数17,即prim[6] |
22 |
|
23 |
for(INT i=1,p=1;i<=limit;i++){ //素数k取i个 |
24 |
p*=prim[k]; |
25 |
getNum(num*p,k+1,sum*(i+1),i); |
26 |
} |
27 |
} |
28 |
|
29 |
INT log2(INT n){ //求大于等于log2（n）的最小整数 |
30 |
INT i = 0; |
31 |
INT p = 1; |
32 |
while(p<n){ |
33 |
p*=2; |
34 |
i++; |
35 |
} |
36 |
return i; |
37 |
} |
38 |
|
39 |
int getrprim(){//反素数的个数 |
40 |
int i = 0; |
41 |
while(n>0){ |
42 |
bestNum = 1; |
43 |
bestSum = 1; |
44 |
getNum(1,0,1,log2(n)); |
45 |
n = bestNum - 1; |
46 |
rprim[i][0]=bestNum; |
47 |
rprim[i][1]=bestSum; |
48 |
i++; |
49 |
} |
50 |
return i; |
51 |
} |