|
1
2
3
4
5
6
7
8
|
反质数：设f(n)表示n个约数的个数，如果对于任意x有0<x<n, f(x) < f(n),那么n就是一个反质数
我们都知道对于任意一个数n，都可以用质数乘积的形式表示出来：x = p1^k1+p2^k2...pn^kn
一个数n如果可以表示成 n = p1^k1 + p2^k2, 那么它的约数的个数就是 （k1+1）*(k2+1)
::k1个p1,可以产生k1个约数，分别是p1^1, p1^2...p1^k1, 同理k2个p2
那么这k1个约数与k2个约数分别相乘，又会得到k1*k2个约数
总的约数的个数就是 k1*k2+k1+k2+1(还有就是1，也是n的一个约数，不要忘记)
|
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 7 typedef long long LL; 8 int p[]={2,3,5,7,11,13,17,19,23,29}; 9 10 LL n, ans, cc; 11 12 void dfs(int pos, int cnt, LL sum){
//pos，p数据的索引；cnt，约数的个数；sum，当前反质数的值 13 if(cnt > cc){ 14 ans = sum; 15 cc = cnt; 16 } 17 if(cnt == cc && ans > sum) 18 ans = sum; 19 if(pos>=10) return; 20 for(int i=1; ; ++i){ 21 sum*=p[pos]; 22 if(sum > n) break; 23 dfs(pos+1, cnt*(i+1), sum); 24 } 25 } 26 27 int main(){ 28 cin>>n; 29 ans = 0; 30 dfs(0, 1, 1); 31 cout<<ans<<endl; 32 return 0; 33 }
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/4415544.html，如需转载请自行联系原作者
