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

时间:2022-01-20 18:37:53

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

[BZOJ1053] [HAOI2007] 反素数ant (搜索)[BZOJ1053] [HAOI2007] 反素数ant (搜索)
 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)的次数。