反素数
定义：对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数.
性质一:一个反素数的质因子必然是从2开始连续的质数.
性质二:p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=....
题目1：Number With The Given Amount Of Divisors
题意：给一个数n，求一个最小的x，使得x的约数 个数为n。
- #include <iostream>
- using namespace std;
- typedef long long LL;
- LL p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
- LL ans;
- LL N;
- void dfs(LL i,LL x,LL n)
- {
- if(n>N) return;
- if(n==N&&ans>x) ans=x;
- for(int k=1;k<=60;k++)
- {
- if(ans/p[i]<x) break;
- dfs(i+1,x*=p[i],n*(k+1));
- }
- }
- int main()
- {
- while(cin>>N)
- {
- ans=5e18;
- dfs(0,1,1);
- cout<<ans<<endl;
- }
- return 0;
- }
题意：求n以内的数，该数的因子数最多，就是要求n以内的最大反素数x。
证明：
在x以内，g(x)最大，在大于x小于n之间不存在因子数大于g(x)的数。
假设存在p，使g(p)>g(x)，则p就是n以内的最大反素数，与x使最大反素数矛盾，顾不存在p。
- #include <stdio.h>
- #include <iostream>
- typedef long long LL;
- int prime[14]={2,3,5,7,11,13,17,19,23,29,31,37,41,43};
- LL max,best;
- LL n;
- void dfs(LL num,int k,LL sum,int limit)
- {
- LL temp;
- if(sum>max)
- {
- max=sum;
- best=num;
- }
- if(sum==max&&best>num) best=num;
- if(k>=14) return;
- temp=num;
- for(int i=1;i<=limit;i++)
- {
- if(temp*prime[k]>n) break;
- temp*=prime[k];
- dfs(temp,k+1,sum*(i+1),i);
- }
- }
- int main()
- {
- while(std::cin>>n)
- {
- dfs(1,0,1,50);
- std::cout<<best<<std::endl;
- }
- return 0;
- }