【zoj2562】反素数

题意：给定一个数N,求小于等于N的所有数当中,约数最多的一个数,如果存在多个这样的数,输出其中最小的一个。(1 <= n <= 10^16)

题目：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=11781

这时一道反素数的应用。

反素数讲解：http://blog.csdn.net/ACdreamers/article/details/25049767

反素数的定义：对于任何正整数，其约数个数记为，例如，如果某个正整数满足：对任意的正整

数，都有，那么称为反素数。

从反素数的定义中可以看出两个性质：

（1）一个反素数的所有质因子必然是从2开始的连续若干个质数，因为反素数是保证约数个数为的这个数尽量小

（2）同样的道理，如果，那么必有

解释一下：

x = p1^r1 * p2^r2 * p3^r3 ..... * pi^ri

x的约数个数=(r1+1) * (r2+1) * ..... * (rn+1) （指数可以填0~ri）

如果约数都为t1*t2*t3*..*tn，又要x最小，那当然就越小的质数指数越大了。

所以我是这样dfs反素数的：

对于当前数 x = p1^r1 * p2^r2 * p3^r3 ..... * pi^ri

如果r[i]+1<=r[i-1] 那么可以继续乘当前的这个素数，否则不可以

dfs的时候就只有两步，

1. 可以的话再乘当前的素数。

2. 尝试乘下一个素数。

所以这道题其实是水题。。就直接找反素数就可以了。。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<iostream>
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 const LL pl=13,INF=(LL)1e16;
10 LL p[14]={0,2,3,5,7,11,13,17,19,23,29,31,37,41};
11 LL n,a1,a2;
12 
13 void dfs(LL x,LL pr,LL r1,LL r2,LL cnt)
14 //x当前的数 pr当前到第几个素数
15 //r1前一个素数的次方数
16 //r2当前的素数的次方数
17 //cnt约数个数
18 {
19     if(x>n) return ;
20     if(cnt>a1) a1=cnt,a2=x;
21     else if(cnt==a1 && x<a2) a2=x;
22     
23     if(pr+1<=pl) dfs(x*p[pr+1],pr+1,r2,1,cnt*2);
24     if(!(pr>1 && r2+1>r1)) dfs(x*p[pr],pr,r1,r2+1,cnt/(r2+1)*(r2+2));
25 }
26 
27 int main()
28 {
29     freopen("a.in","r",stdin);
30     freopen("me.out","w",stdout);
31     while(scanf("%lld",&n)!=EOF)
32     {
33         if(n==1) {printf("1
");continue;}
34         a1=0,a2=INF;
35         dfs(2,1,0,1,2);
36         printf("%lld
",a2);
37     }
38     return 0;
39 }

zoj2562