反素数
思路:
看见题目首先是暴力做法,也就是筛一遍N以内的约数个数比大小,但是N是2e9,绝无可能挨个求解,联想到约数个数相关性质的第三条,极限int值下的约数个数只有2000多个,可能是从这里进行突破,2000这个数据很小感觉可以承受$n^2$logn的复杂度,题目需要找到小于N的最大的“反素数”,分开一下也就是“最大”和“反素数”,首先,质数的约数仅有自己和1这两个,在大一点的条件下一般不可能是素数,那能不能通过质数来反向筛掉合数呢,也不行,因为大合数的约数也可能是小合数,但是可以通过小的质数来将大合数转换成基本算数定理的形式,这样就可以用性质1的求约数个数公式来快速算出某个大数的约数个数,可是这个时间复杂度也是感觉过不去的,因为需要线性扫一遍
分析:
将1~N中的最大的反素数转换成了最大约数个数的那个最小的数,分析一下这个约数的性质:
1.根据性质4,可以发现最大合数里面不同的质因子最多只有9个
2.每个质因子最大次方只有30,因为$2^{31}$严格大于2e9了
3.所以质因子次数一定递减
所以,这些性质的数据范围都很小很小,完全可以直接用爆搜去枚举质因子的次方
代码:
//wengyan17的init
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define cerr(x) std::cerr << (#x) << " is " << (x) << '\n'
#define IOS std::ios::sync_with_stdio(false);std::cin.tie(nullptr);
#define PII pair<int, int>
#define pdd pair<double,double>
#define LL long long
#define rep(i,a,b) for (int i = a; i <= b; i ++)
#define per(i,b,a) for (int i = b; i >= a; i --)
const double CLOCKS_PER_SECOND = ((clock_t)1000);
const double CLOCKS_PER_MILLISECOND = ((clock_t)1);
const int N = 2e5 + 10, mod = 1e9 + 7;
//#define x first
//#define y second
int n;
int maxnum, maxd;
int primes[9] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
void dfs(int u, int last, int p, int s) {
if (s > maxd || s == maxd && p < maxnum) {
maxnum = p, maxd = s;
}
if (u == 9) {
return;
}
for (int i = 1; i <= last; i ++) {
if ((LL)p * primes[u] > n) {
break;
}
p *= primes[u];
dfs(u + 1, i, p, s * (i + 1));
}
}
int main() {
cin >> n;
dfs(0, 30, 1, 1);
cout << maxnum << endl;
return 0;
}