兰道函数
对于所有非负整数，兰道函数$g(n)$定义为对称群$S_{n}$的所有元素的秩之中，最大的一个。或者说，$g(n)$是$n$的所有整数分拆之中的最小公倍数。
例如${\displaystyle 5=2+3}, {\displaystyle lcm(2,3)=6}$没有其他5的分割方式能得出一个更大的最小公倍数，故此${\displaystyle g(5)=6}$
{\displaystyle \lim _{n\to \infty }{\frac {\ln(g(n))}{\sqrt {n\ln(n)}}}=1}
(摘自WikiPedia – 蘭道函數)
OEIS – A000793 – landau function
g(0) = 1, g(1) = 1, g(2) = 2, g(3) = 3, g(4) = 4, g(5) = 6, g(6) = 6, g(7) = 12, g(8) = 15, …
上面的我也不懂
代码实现
从兰道函数的定义得知，我们要求的是将 n 分成 \lbrace x_1, x_2, x_3…x_k \rbrace后， max\big\lparen lcm \lparen x_1, x_2, x_3…x_k\rparen \big\rparen。
暴力拆分
// C++ program for the above approach
#include
using namespace std;
// To store Landau's function of the number
int Landau = INT_MIN;
// Function to return gcd of 2 numbers
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
// Function to return LCM of two numbers
int lcm(int a, int b)
{
return (a * b) / gcd(a, b);
}
// Function to find max lcm value
// among all representations of n
void findLCM(vector& arr)
{
int nth_lcm = arr[0];
for (int i = 1; i < arr.size(); i++)
nth_lcm = lcm(nth_lcm, arr[i]);
// Calculate Landau's value
Landau = max(Landau, nth_lcm);
}
// Recursive function to find different
// ways in which n can be written as
// sum of atleast one positive integers
void findWays(vector& arr, int i, int n)
{
// Check if sum becomes n,
// consider this representation
if (n == 0)
findLCM(arr);
// Start from previous element
// in the representation till n
for (int j = i; j <= n; j++) {
// Include current element
// from representation
arr.push_back(j);
// Call function again
// with reduced sum
findWays(arr, j, n - j);
// Backtrack - remove current
// element from representation
arr.pop_back();
}
}
// Function to find the Landau's function
void Landau_function(int n)
{
vector arr;
// Using recurrence find different
// ways in which n can be written
// as a sum of atleast one +ve integers
findWays(arr, 1, n);
// Print the result
cout << Landau;
}
// Driver Code
int main()
{
// Given N
int N = 4;
// Function Call
Landau_function(N);
return 0;
}
时间复杂度：\mathcal{O}(2^N)
空间复杂度：\mathcal{O}(N^2)
暴力拆分不是很好的策略，现证明 x_i = p ^ A，其中 p 为质数。
(update 2023.11.11)
假设我们拆分出来一个 x_i 是合数，那么该数对 lcm 的贡献最多是 x_i 。设 x_i = m \times q, (m, q) = 1, m > 1, n > 1。最后的贡献为 n \times m，那如果 n,m 互质，但有一个不是质数，这个数可以继续拆分。
现在考虑如何拆分，可以将每个这样的 x_i 拆成 \big\lbrace m, q, (mq -m – q) \big\rbrace，可以证明，mq – m – q \gt 0，lcm 不会变小，和没有变化。那么就可以将 x_i 一直拆下去，直到全部拆成质数。
考虑 dp
令 dp[i][j] 表示数字 i 由前 j 个质数组成的最大取值。那么再枚举一个 k ，表示 p_j 的次数。
TLE Code
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 2005;
bool prime[N];
int p[N];
vector<vector<long long>> dp(N, vector<long long>(N));
vector<long long> ans(N);
int k;
void isprime() {
k = 1;
fill(prime, prime + N, true);
for (int i = 2; i < N; i++) {
if (prime[i]) {
p[k++] = i;
for (int j = i + i; j < N; j += i) {
prime[j] = false;
}
}
}
}
long long max(long long a, long long b) {
return (a > b) ? a : b;
}
void Work() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < k; j++) {
dp[i][j] = 1;
}
}
for (int i = 1; i < k; i++) {
dp[2][i] = 2;
}
for (int i = 3; i < N; i++) {
for (int j = 1; j < k; j++) {
dp[i][j] = dp[i][j - 1];
int tmp = p[j];
while (i >= tmp) {
dp[i][j] = max(dp[i][j], dp[i - tmp][j - 1] * tmp);
tmp *= p[j];
}
}
}
ans[0] = ans[1] = 1;
ans[2] = 2;
for (int i = 3; i < N; i++) {
ans[i] = 0;
for (int j = 1; j < k; j++) {
ans[i] = max(ans[i], dp[i][j]);
}
}
}
int main() {
isprime();
Work();
int n;
while (cin >> n) {
cout << ans[n] << endl;
}
return 0;
}
我们发现这个东西是个完全背包，一次有至多 n 种品种，逐次减小。那么 dp 可以优化到一维。
AC Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const int N = 4e4 + 10;
const double pi = acos(-1.0);
int n;
int cnt, p[5000], a[5000], flag[N];
double dp[N];
double l[N];
void get_prime() {
l[1]=0;
for(int i = 2; i < N; i++) {
l[i] = log(1.0 * i);
if(!flag[i]) p[++cnt] = i;
for(int j = 1; j <= cnt; j++) {
if(i * p[j] > N) break;
flag[i * p[j]] = 1;
if(i % p[j] == 0) break;
}
}
}
inline void solve() {
for(int i = 1; i <= cnt; i++) {
int tot = 0;
for(int j = p[i]; j <= n; j *= p[i]) a[++tot] = j;//tot表示p能有多少种可能（完全背包！）
for(int j = n; j >= a[1]; j--) {
for(int k = 1; k <= tot; k++) {
if(j >= a[k]) dp[j] = max(dp[j], dp[j - a[k]] + l[a[k]]);//看到这个方程是不是豁然开朗
}
}
}
}
int main()
{
// freopen("icecream.in", "r", stdin);
// freopen("icecream.out", "w", stdout);
scanf("%d", &n);
get_prime();
// cout << cnt;
// Work();
solve();
printf("%.7f", dp[n]);
return 0;
}
的影响