P1463 [POI2001][HAOI2007]反素数

反素数

定义

“反素数”(antiprime number)也称为“高合成数”(highly composite number)。

设 $\tau(n)=\sum_{d|n} 1$，表示 $n$ 的所有因数个数。

若正整数 $q$ 满足：对于 $\forall x\in\mathbb Z_{\geqslant 1},x < q$ 都有 $\tau(q) > \tau(x)$ 则称 $q$ 为反素数。

例如前几个反素数为 $1, 2, 4, 6, 12$。

性质

命题1：设（标准分解） $q=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_s^{\alpha_s}$ 且 $q$ 为反素数，则一定有 $\alpha_1 \geqslant \alpha_2\geqslant\cdots\geqslant\alpha_s$。
其中 $p_1 < p_2 < \cdots < p_s$。

证明：

由组合性质得：$q$ 的因数个数 $\tau(q)=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_s+1)$。

反设，不失一般性，设 $\alpha_1 < \alpha_2$，令 $q'=p_1^{\alpha_2}p_2^{\alpha_1}\cdots p_s^{\alpha_s}$。

则 $\tau(q)=\tau(q')$ 且 $q' < q$，与 $q$ 为反素数矛盾，则原命题成立。

QED

推论2：设 $q$ 为反素数，则其素因数必然是连续的，即若 $\alpha_s > 0$ 则 $\forall i \in [1, s], \alpha_i > 0$。

求不超过 $N$ 的最大的反素数

而且我们又可以发现，可以通过已有的反素数推出下一个最小的反素数，我们构建一个大根堆，以数值大小为键值。

我们在已有的反素数基础上，在满足上述反素数的性质的基础上，乘上一个素数放入堆中，则下一个堆顶元素，一定就是下一个最小的反素数。

以此类推，我们可以求出连续的所有反素数（在一定范围内）。

总复杂度 $O(\log N\log N)$，第一个 $\log$ 是堆的复杂度，第二个 $\log$ 是每次枚举素数的复杂度。

Luogu - P1463 [POI2001][HAOI2007]反素数

P1463 [POI2001][HAOI2007]反素数

题意

给定一个 $N$，求不超过 $N$ 的最大的反素数。

数据范围：$1\leqslant N \leqslant 2\times 10^9$。

思路

使用上述的结论和思路即可。

下面是前几个素数之积，用来判断至少要枚举的素数个数用的。

2 2
3 6
5 30
7 210
11 2310
13 30030
17 510510
19 9699690
23 223092870
29 6469693230

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
const int N = 1e5 + 10;
bool vis[N];
vi prim;
void Euler(int n) {
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) prim.pb(i);
		for (auto j : prim) {
			int t = i * j;
			if (t > n) break;
			vis[t] = 1;
			if (i % j == 0) break;
		}
	}
}
int p[9] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
struct Node {
	int num, fac;
	vi mi;
	Node(int a, int b, vi &c) : num(a), fac(b), mi(c){}
	friend bool operator < (const Node &a, const Node &b) {
		return a.num > b.num;
	}
};
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	//Euler(1e5);
	//int mul = 1;
	//int sz = prim.size();
	//for (int i = 0; i < 9; i++) {
	//	mul *= prim[i];
	//	cout << prim[i] << ", ";
	//}
	int n, mul = 1, ans = 1, fac = 0;
	cin >> n;
	vi now(9);
	priority_queue<Node> q;
	q.push(Node(1, 1, now));
	while (!q.empty()) {
		Node tmp = q.top();
		q.pop();
		if (tmp.num > n) break;
		if (tmp.fac <= fac) continue;
		ans = tmp.num;
		fac = tmp.fac;
		for (int i = 0; i < 9; i++) {
			if (!i || tmp.mi[i] < tmp.mi[i-1]) {
				now = tmp.mi;
				now[i]++;
				q.push(Node(tmp.num * p[i], tmp.fac / (tmp.mi[i]+1) * (now[i]+1), now));
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

51nod - 1061 最复杂的数 V2

1061 最复杂的数 V2

题意

给定一个 $N$，求不超过 $N$ 的最大的反素数和其包含的约数个数。

数据范围：$1\leqslant N \leqslant 10^{200}$。

思路

做法和上道题一模一样，加上高精度即可，还是要打表，最后二分答案即可。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
const int N = 1000 + 10;
int vis[N];
vi prim;
void Euler(int n) {
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) prim.pb(i);
		for (auto j : prim) {
			int t = i * j;
			if (t > n) break;
			vis[t] = 1;
			if (i % j == 0) break;
		}
	}
}
const int power = 8;
const int base = 1e8;
struct longnum {
	vi a;
	longnum(){a.clear();}
	longnum(string s) {
		a.clear();
		int n = s.size(), now = 0;
		reverse(s.begin(), s.end());
		for (int i = 0, w = 1; i < n; i++, w *= 10) {
			if (i != 0 && i % power == 0) {
				a.pb(now);
				now = 0;
				w = 1;
			}
			now += w * (s[i] - '0');
		}
		if (now != 0) a.pb(now);
	}
	void print() {
		int n = a.size();
		printf("%lld", a[n-1]);
		for (int i = n-2; i >= 0; i--) printf("%0*lld", power, a[i]);
	}
	bool operator < (const longnum &x) const &{
		if (a.size() != x.a.size()) return a.size() < x.a.size();
		int n = a.size();
		for (int i = n-1; i >= 0; i--) {
			if (a[i] != x.a[i]) return a[i] < x.a[i];
		}
		return 0;
	}
	bool operator > (const longnum &x) const &{
		if (a.size() != x.a.size()) return a.size() > x.a.size();
		int n = a.size();
		for (int i = n-1; i >= 0; i--) {
			if (a[i] != x.a[i]) return a[i] > x.a[i];
		}
		return 0;
	}
	bool operator <= (const longnum &x) const &{
		return !(*this > x);
	}
	longnum operator * (const int &x) const &{
		longnum ret;
		int n = a.size();
		vi &b = ret.a;
		b = vi(n);
		for (int i = 0; i < n-1; i++) {
			b[i] += a[i] * x;
			b[i+1] += b[i] / base;
			b[i] %= base;
		}
		b.back() += a[n-1] * x;
		while (b.back() >= base) {
			int t = b.back() / base;
			b.back() %= base;
			b.pb(t);
		}
		return ret;
	}
};
struct Node {
	longnum num, fac;
	vi mi;
	Node(longnum a, longnum b, vi &c) : num(a), fac(b), mi(c){}
	bool operator < (const Node &x) const &{
		return num > x.num;
	}
};
signed main(){
#ifdef _DEBUG
	FILE *file = freopen("out", "w", stdout);
#endif
	Euler(1000);
	string s = "1";
	for (int i = 0; i < 200; i++) s.pb('0');
	longnum mx(s), fac("0");
	vector<longnum> ans, factNum;
	vi now;
	priority_queue<Node> q;
	q.push(Node(longnum("1"), longnum("1"), now));
	while (!q.empty()) {
		Node tmp = q.top();
		q.pop();
		if (tmp.num > mx) break;
		if (tmp.fac <= fac) continue;
		ans.pb(tmp.num);
		factNum.pb(tmp.fac);
		fac = tmp.fac;
		int sz = tmp.mi.size();
		for (int i = 0; i < sz; i++) {
			if (!i || tmp.mi[i] < tmp.mi[i-1]) {
				now = tmp.mi;
				now[i]++;
				longnum f("1");
				for (auto j : now) f = f * (j+1);
				q.push(Node(tmp.num * prim[i], f, now));
			}
		}
		now = tmp.mi;
		now.pb(1);
		longnum f("1");
		for (auto i : now) f = f * (i+1);
		q.push(Node(tmp.num * prim[sz], f, now));
	}
	int T;
	cin >> T;
	while (T--) {
		string s;
		cin >> s;
		int p = upper_bound(ans.begin(), ans.end(), longnum(s)) - ans.begin();
		ans[p-1].print();
		putchar(' ');
		factNum[p-1].print();
		putchar('\n');
	}
	return 0;
}

POJ 2886: Who Gets the Most Candies?

见 Blog。