[BZOJ1053] [HAOI2007] 反素数ant (搜索)

Description

　　对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。
　　如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。
　　现在给定一个数N，你能求出不超过N的最大的反质数么？

Input

　　一个数N（1<=N<=2,000,000,000）。

Output

　　不超过N的最大的反质数。

Sample Input

1000

Sample Output

840

HINT

Source

Solution

　　额，一些玄学证明了这个数的素因子只可能是前12个素数，搜索即可。

　　。。。典型O(跑得过) 233

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll p[13] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
 5 ll n, ans, gans;
 6  
 7 void DFS(ll x, ll gx, ll id, ll cnt)
 8 {
 9     if(gx == gans && x < ans) ans = x;
10     if(gx > gans) ans = x, gans = gx;
11     for(int i = 1; i <= cnt; i++)
12         if(x * p[id] <= n)
13             DFS(x = x * p[id], gx * (i + 1), id + 1, i);
14 }
15  
16 int main()
17 {
18     cin >> n;
19     DFS(1, 1, 1, 20);
20     cout << ans << endl;
21     return 0;
22 }

View Code

　　解释一下DFS的参数：

　　x:当前计算的数为x

　　gx:g(x)的值

　　id:当前要枚举第id个素数

　　cnt:当前第id-1个素数的次数为cnt。玄学证明了p[id]的次数一定不超过p[i](0 < i < id)的次数。