反素数

做题碰到了反素数，学习了下http://blog.csdn.net/acdreamers/article/details/25049767

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

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

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

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

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

More Divisors

ZOJ - 2562

题意：求小于n的因子最多的数。

 1 #include <cstdio>
 2 #include <iostream>
 3 using namespace std;
 4 #define ll long long
 5 ll n,ans;
 6 ll best;
 7 int pri[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
 8 //ct用到了性质2
 9 void dfs(int d,int ct,ll temp,ll num){
10     if(d>=16) return;
11     if(num>best||num==best&&ans>temp){
12         ans=temp;
13         best=num;
14     }
15     for(int i=1;i<=ct;i++){
16         if(n/pri[d]<temp) break;
17         temp*=pri[d];
18         dfs(d+1,i,temp,num*(i+1));  //选i个pri[d],因子变为num*(i+1)
19     }
20 }
21 int main(){
22     while(scanf("%lld",&n)!=EOF){
23         ans=1e18;
24         best=0;
25         dfs(0,60,1,1);
26         printf("%lld
",ans);
27     }
28 }

View Code

Number With The Given Amount Of Divisors

CodeForces - 27E

题意：求因数为n的最小正整数。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 int n;
 5 ll ans;
 6 int pri[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
 7 
 8 void dfs(int d,int ct,ll temp,int num){
 9     if(num>n) return ;
10     if(num==n&&temp<ans) ans=temp;
11     for(int i=1;i<=ct;i++){
12         if(ans<pri[d]*temp) break;
13         dfs(d+1,i,temp*=pri[d],num*(i+1));
14     }
15 }
16 int main(){
17     scanf("%d",&n);
18     ans=1e18;
19     dfs(0,60,1,1);
20     printf("%lld
",ans);
21 }

View Code

小明系列故事——未知剩余系

HDU - 4542

题意：两种查询，0是查询最小正整数x满足1到x中x的约数为k个，1是查询最小正整数x，满足1到x中x的不是x的约数的整数有k个。

先预处理出ans[x]，表示不是约数的正整数有x个的最小正整数。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 const ll inf=(ll)1<<62;
 6 const int maxn=48000;
 7 int pri[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
 8 int d[maxn],ans[maxn];
 9 void init(){
10     for(int i=1;i<maxn;i++) {d[i]=i;ans[i]=0;}
11     for(int i=1;i<maxn;i++){
12         for(int j=i;j<maxn;j+=i) d[j]--;
13         if(!ans[d[i]]) ans[d[i]]=i;
14     }
15 }
16 ll res;
17 int c,k;
18 void dfs(int d,int ct,ll temp,int num){
19     if(num>k||d>=16) return;
20     if(num==k&&temp<res) res=temp;
21     for(int i=1;i<=ct;i++){
22         if(res/pri[d]<temp||(num*(i+1)>k)) break;
23         temp*=pri[d];
24         if(k%(num*(i+1))==0)
25             dfs(d+1,i,temp,num*(i+1));
26     }
27 }
28 int main(){
29     int t;
30     scanf("%d",&t);
31     int kase=0;
32     init();
33     while(t--){
34         scanf("%d%d",&c,&k);
35         if(c) res=ans[k];
36         else {
37             res=inf;
38             dfs(0,62,1,1);
39         }
40         printf("Case %d: ",++kase);
41         if(res==0) puts("Illegal");
42         else if(res==inf) puts("INF");
43         else printf("%lld
",res);
44     }
45 }

View Code