ZOJ-2562 More Divisors 反素数

时间:2023-03-08 17:09:48

题意:给定一个数N,求小于等于N的所有数当中,约数最多的一个数,如果存在多个这样的数,输出其中最大的一个。

分析:反素数定义:对于任何正整数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>=....

那题题目相当于求解小于等于N中,最大的反素数。搜索即可。这个搜索的速度是很快的。

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
using namespace std; typedef long long LL; LL n;
vector<int>vp;
map<int,LL>mp; bool isprime(int x) {
if (x < ) return false;
if (x == ) return true;
int LIM = (int)sqrt(x);
for (int i = ; i <= LIM; ++i) {
if (x % i == ) return false;
}
return true;
} void pre() {
for (int i = ; i < ; ++i) {
if (isprime(i)) vp.push_back(i);
}
} void dfs(int p, int exp, int g, LL num) {
if (num * vp[p] > n) {
if (mp.count(g)) mp[g] = min(mp[g], num);
else mp[g] = num;
return;
}
num *= vp[p];
for (int i = ; num <= n && i <= exp; ++i, num *= vp[p]) {
dfs(p+, i, g*(i+), num);
}
} int main() {
pre();
while (scanf("%lld", &n) != EOF) {
mp.clear();
dfs(, , , );
printf("%lld\n", (--mp.end())->second);
printf("size = %d\n", mp.size());
}
return ;
}