概述

定义

记正整数n因子个数为f(n),如f(6) = 4
若某个正整数n满足对于任意i(0<i<n),有f(i) < f(n) 则称n为反素数

性质

  1. 一个反素数的质因子必然是从2开始的连续若干个质数
  2. 若$n = 2^{e_1} * 3^{e_2} * 5^{e_3}… $ 则有 $e_1 \geq e_2 \geq e_3 \geq …$

因为反素数保证约数个数为x的n尽量小

题目

求因子个数

$sum=(e_1+1)(e_2+1)…(e_m+1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
LL cal(int x,int y) //a*b因子个数
{
LL res=1;
int c,cnt;
for(;x>1 || y>1;){
cnt=1;
c=min(p[x],p[y]);
for(;p[x]==c;x/=c) ++cnt;
for(;p[y]==c;y/=c) ++cnt;
res*=cnt;
}
return res;
}

void init()
{
memset(p,0,sizeof p); //p[i]表示i的最小质因子
int tot=0;
for(int i=2;i<=N;++i){
if(!p[i]) primes[tot++]=p[i]=i;
for(int j=0;j<tot && primes[j]<=p[i] && primes[j]<=N/i; ++j) p[i*primes[j]]=primes[j];
}
p[1]=INF;
for(int i=1;i<=N;++i) fac[i]=cal(i,1);
}

求最小的x满足x约数个数为n

CF27E

根据反素数性质,我们考虑dfs,以每个 $p_i$ 为一层,枚举 $e_i$ ,更新最小值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef unsigned long long ULL;
ULL ans ;
bool vis[1010];
int n;
vector<int> primes;

void init()
{
primes.clear();
memset(vis,0,sizeof vis);
for(int i=2; primes.size()<60 ;++i)
{
if(!vis[i])
{
primes.push_back(i);
for(int j=i+i;j<1000;j+=i) vis[j] = 1;
}
}
}

void dfs(int num,int p,ULL res)
{
if(num>n) return;
if(num==n && res<ans) ans = res;
for(int i=1;i<60;++i)
{
if(res*primes[p] > ans) break;
dfs(num*(i+1),p+1,res *= primes[p]);
}
}

int main()
{
init();
while(scanf("%d",&n)==1)
{
ans = 1e19;
dfs(1,0,1);
printf("%llu\n",ans);
}
return 0;
}

求1-n因子数目最多的数

zoj2562

和上面的思路差不多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;

typedef unsigned long long ULL;
vector<int> primes;
bool vis[1010];
ULL n,ans;
int rec;

void init()
{
primes.clear();
for(int i=2;primes.size()<54;++i)
{
if(!vis[i])
{
primes.push_back(i);
for(int j=i+i;j<1000;j+=i) vis[j] = 1;
}
}
}

void dfs(int k,int p,ULL cur)
{
if(rec < k || (rec==k && ans > cur ))
{
rec = k;
ans = cur;
}
for(int i=1;i<55;++i)
{
if(cur * primes[p] > n) break;
dfs(k*(i+1),p+1,cur *= primes[p]);
}
}

int main()
{
init();
while(scanf("%llu",&n)==1)
{
rec = 1;
ans = n;
dfs(1,0,1);
printf("%llu\n",ans);
}
return 0;
}

ural1748

和上一道题一样,不过数据范围大。
需要根据第二个反素数性质剪枝,即设置一个limit,每层幂次只枚举到limit

hdu4542

给出一个数K和两个操作

  • 如果操作是0,就求出一个最小的正整数X,满足X的约数个数为K
  • 如果操作是1,就求出一个最小的X,满足X的约数个数为X-K

操作0即求反素数,操作1由筛法处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;

typedef long long ULL;

const ULL INF = (1LL<<62)+1;
const int maxn = 50010;
ULL ans;

bool vis[100];
vector<int> primes;
int d[maxn],ans[maxn];

int n,type;

void init()
{
memset(vis,0,sizeof vis);
primes.clear();

for(int i=2;primes.size()<16;++i)
{
if(!vis[i])
{
primes.push_back(i);
for(int j=i+i;j<100;j+=i) vis[j] = 1;
}
}

for(int i=1;i<maxn;++i) d[i] = i;
for(int i=1;i<maxn;++i)
{
for(int j=i;j<maxn;j+=i) --d[j];
if(!ans[d[i]]) ans[d[i]] = i;
}
}

void dfs(int p,int k,ULL cur,int limit)
{
if(k > n) return;
if(k == n && ans > cur) ans = cur;
for(int i = 1;i <= limit; ++i)
{
if(ans/primes[p] < cur || k*(i+1) > n) break;
cur *= primes[p];
if(n%(k*(i+1)) == 0)
dfs(p+1,k*(i+1),cur,i);
}
}


int main()
{
init();
int T;
scanf("%d",&T);
for(int z=1;z<=T;++z)
{
scanf("%d %d",&type,&n);
printf("Case %d: ",z);
if(type)
ans = ans[n];
else
{
ans = INF;
dfs(0,1,1,62);
}
if(ans == 0) puts("Illegal");
else if(ans >= INF) puts("INF");
else printf("%I64d\n",ans);
}
return 0;
}

注意

在dfs时,cur有可能爆long long,所以判断用 ans/priems[p] < cur
根据反素数性质剪枝:

  • $e_1 \geq e_2 \geq e_3 …$ 加一个limit
  • 若求因子个数为n个,则当前因子个数必可整除n (n%(k*(i+1)) == 0)

打表

由于反素数非常稀疏,所以可以直接打表
1e18 以内的反素数(167个)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
LL anti_primes[167]={1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,
1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,
83160,110880,166320,221760,277200,332640,498960,554400,665280,720720,
1081080,1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640,
10810800,14414400,17297280,21621600,32432400,36756720,43243200,61261200,
73513440,110270160,122522400,147026880,183783600,245044800,294053760,
367567200,551350800,698377680,735134400,1102701600,1396755360,
2095133040,2205403200,2327925600,2793510720,3491888400,4655851200,
5587021440,6983776800,10475665200,13967553600,20951330400,27935107200,
41902660800,48886437600,64250746560,73329656400,80313433200,97772875200,
128501493120,146659312800,160626866400,240940299600,293318625600,
321253732800,481880599200,642507465600,963761198400,1124388064800,
1606268664000,1686582097200,1927522396800,2248776129600,3212537328000,
3373164194400,4497552259200,6746328388800,8995104518400,9316358251200,
13492656777600,18632716502400,26985313555200,27949074753600,
32607253879200,46581791256000,48910880818800,55898149507200,
65214507758400,93163582512000,97821761637600,130429015516800,
195643523275200,260858031033600,288807105787200,391287046550400,
577614211574400,782574093100800,866421317361600,1010824870255200,
1444035528936000,1516237305382800,1732842634723200,2021649740510400,
2888071057872000,3032474610765600,4043299481020800,6064949221531200,
8086598962041600,10108248702552000,12129898443062400,18194847664593600,
20216497405104000,24259796886124800,30324746107656000,36389695329187200,
48519593772249600,60649492215312000,72779390658374400,74801040398884800,
106858629141264000,112201560598327200,149602080797769600,224403121196654400,
299204161595539200,374005201994424000,448806242393308800,673209363589963200,
748010403988848000,897612484786617600,1122015605983272000,1346418727179926400,
1795224969573235200,2244031211966544000,2692837454359852800,3066842656354276800,
4381203794791824000,4488062423933088000,6133685312708553600,8976124847866176000,
9200527969062830400};

参考