拆分 - 题目列表

答案模998244353,那么就需要把答案计算出来(加,乘),不应该一个一个枚举出来(TLE),
应该是计数DP(背包可以进行分类计数)
从总体688 消除一部分后(比如消除86,剩余8),问题应该变成了8的组合方案了
因子具有传递性,688的因子的因子,就是688的因子. 那么所有的备选物品都就是688的所有因子.(知道了所有的备选的物品)
那么可以用01背包吗?

考虑688:

考虑到40

2 x 20

4 x 10

2 x 4 x 5 -> g[]

5 x 8

显然可以想到一个暴力, 40的所有因子2 4 5 8 10 20 40 ,通过枚举01序列来得到所有的组合,然后过滤掉不合法的方案,剩余合法的方案.

这说明备选物品最多选一次:01背包?

然后对合法的方案进行分类

f[8][40] 表示前8个元素组成40的方案数字
f[8][40] = f[7][40] + f[7][1] ,一个用40,一个不用40.

还是直觉的不太对(没有做过类似的题目,用背包,枚举一下40的dp)

前0个物品:0

容量: 1 2 4 5 8 10 20 40
方案: 1 0 0 0 0 0  0  0


前1个物品:2

容量: 1 2 4 5 8 10 20 40
方案: 1 1 0 0 0 0  0  0

f[1][2] = f[0][1] + f[0][2] = 1
          使用2      不使用2
f[1][4] = f[0][2] + f[0][4] = 0
          使用2      不使用2
....


前2个物品:2 4

容量: 1 2 4 5 8 10 20 40
方案: 1 1 1 0 1 0  0  0

前3个物品:2 4 5

容量: 1 2 4 5 8 10 20 40
方案: 1 1 1 1 1 1  1  1

f[3][40] = f[2][8] + f[2][40] = 0
          使用5      不使用5

前4个物品:2 4 5 8

容量: 1 2 4 5 8 10 20 40
方案: 1 1 1 1 2 1  1   2

前5个物品:2 4 5 8 10

容量: 1 2 4 5 8 10 20 40
方案: 1 1 1 1 2 2  2   3

前6个物品:2 4 5 8 10 20

容量: 1 2 4 5 8 10 20 40
方案: 1 1 1 1 2 2  3   4

前7个物品:2 4 5 8 10 20 40

容量: 1 2 4 5 8 10 20 40
方案: 1 1 1 1 2 2  3   5

好像是对的,写一个二维的背包,然后和baoli.cpp进行对拍试一试

测试了1000以内的数字都是对的,

cpp

// 40 = 2x4x5 ->  此时需要求8 由 [5] 以内的元素组合完成的数量
#include <bits/stdc++.h>
#include <vector>
typedef long long ll;
const int maxn = 1e5;

int n;
const int mod = 998244353;
ll t;

ll ans;
int f[1000+5][1000+5]; //上限数字1000
std::vector<int> fac;

//得到所有的因子
void get_fac() {
    fac.clear();

    fac.clear();
    for(ll i = 2;i*i <= t ;++i ) // i: 2->t
    {
        if( t % i == 0)  {
            fac.push_back(i);
            if( t / i != i)  //放置放两遍
                fac.push_back(t / i);
        }

    }

    std::sort(fac.begin(),fac.end());
    fac.push_back(t);
    // for(auto v: fac) std::cout << v << " ";
    // std::cout  << "\n";
}

void dp() {
    memset(f,0,sizeof(f));
    f[0][1] = 1;

    //枚举物品
    for(int k = 0 ;k<fac.size(); k++)
    {
        int i = k+1;
        //枚举容量
        for(int j = 1 ;j <= t;j++) {
            f[i][j] = f[i-1][j];
            if( j >= fac[k] && j % fac[k]== 0) {
                //使用这个物品
                f[i][j] += f[i-1][j / fac[k] ];
            }
        }

        // std::cout << i << ": ";
        // for(int j = 1 ;j <= t;j++) 
        //     std::cout << f[i][j] << " ";
        // std::cout  << "\n";
    }
    std::cout << (f[fac.size()][t] - 1) % mod << "\n";

}

int main (int argc, char *argv[]) {
    int T;
    std::cin >> T;
    while (T--) {
        std::cin >> t;
        get_fac();
        dp();
        
    }
    
    return 0;
}

优化

显然下面是优化. 空间不可能开 $10^12$ ,但是发现只有因子才是有的空间,不禁要问最多有多少个因子呢?

这是一个非常好的问题。在算法竞赛（尤其是数论题）中，对数据规模的直觉和边界分析非常重要。

对于 $N \le 10^{12}$ ，为什么我能断定因子数量最多只有 6720 个？

这涉及到数论中的一个概念：反素数（Anti-Prime） 或者叫 高合成数（Highly Composite Number）。

1. 什么是“因子最多”的数？

如果要让一个数 $n$ 的因子数量最多，根据算术基本定理，我们需要尽可能让它由最小的质数（2, 3, 5, 7…）组成，并且指数尽可能分配得均匀。

公式：

n = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}

因子个数：

\tau(n) = (a_1+1) \times (a_2+1) \times \dots \times (a_k+1)

构造策略：为了让 $\tau(n)$ 最大，且 $n \le 10^{12}$ ：

我们必须只选最小的几个质数：2, 3, 5, 7, 11, 13…
指数必须是递减的（即 $a_1 \ge a_2 \ge a_3 \dots$ ），否则我们交换指数，数值变小但因子数不变，就不是最优的了。(数值边小了,因子数不变,那这个数就不是极限,反证法)

实战推算 $10^{12}$ 的极限

我们可以写一个小脚本，或者手动凑一下。

在 $10^{12}$ 范围内，拥有最多因子的那个数（冠军）是 963,761,198,400。

它的质因数分解是：

n = 2^6 \times 3^4 \times 5^2 \times 7^2 \times 11^1 \times 13^1 \times 17^1 \times 19^1

我们可以验证一下大小：

963,761,198,400 < 10^{12} \text{ (即 1,000,000,000,000)}

它的因子数量计算：

\begin{aligned} \text{Count} &= (6+1) \times (4+1) \times (2+1) \times (2+1) \times (1+1) \times (1+1) \times (1+1) \times (1+1) \\ &= 7 \times 5 \times 3 \times 3 \times 2 \times 2 \times 2 \times 2 \\ &= \mathbf{6720} \end{aligned}

所以，对于 $10^{12}$ 以内的任何数，因子个数绝对不会超过 6720。

其实根本没有那么复杂,写一个小代码,来枚举

cpp


#include <iostream>

using namespace std;

typedef long long ll; // 定义 ll 为 long long，防止 10^12 溢出

// 全局变量
const ll LIMIT = 1e12; // 搜索上限
// 质数表 (足够用到 10^12)
int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
ll max_divisors = 0;
ll best_num = 0;

/**
 * dfs 搜索
 * @param idx: 当前正在处理第几个质数 (primes[idx])
 * @param current_val: 当前的数值
 * @param current_divisors: 当前的因子数量
 * @param last_exp: 上一个质数的指数 (用于剪枝：当前指数不能超过上一个)
 */
void dfs(int idx, ll current_val, ll current_divisors, int last_exp) {
    // 1. 更新答案 (对应 Python 开头的逻辑)
    if (current_divisors > max_divisors) {
        max_divisors = current_divisors;
        best_num = current_val;
    } else if (current_divisors == max_divisors) {
        // 如果因子数量相同，取数值更小的 (题目通常要求最小的反素数)
        if (current_val < best_num) best_num = current_val;
    }

    // 边界条件：如果没有质数可用了，返回
    if (idx >= 16) return;

    ll p = primes[idx];
    ll next_val = current_val;

    // 2. 枚举当前质数的指数 e
    // 必须满足 e <= last_exp (保证指数递减，这是反素数的性质)
    for (int e = 1; e <= last_exp; ++e) {
        // 检查是否超过 limit
        // 使用除法判断防止 next_val * p 溢出 (虽然 long long 够大，但这是好习惯)
        if (LIMIT / p < next_val) break; 
        
        next_val *= p;
        
        // 递归处理下一个质数
        // 因子数量计算公式：(a1+1)*(a2+1)... 所以乘上 (e+1)
        dfs(idx + 1, next_val, current_divisors * (e + 1), e);
    }
}

int main() {
    // 初始调用：第0个质数，数值1，因子数1，上个指数给个大数(比如60)
    dfs(0, 1, 1, 60);

    cout << "Range: 10^12" << endl;
    cout << "Best Number: " << best_num << endl;
    cout << "Divisors: " << max_divisors << endl;

    return 0;
}

我们开以个f[2][10000],然后进行滚动数组(这样不用考虑容量的从大到小,还是从小到大了,如果使用一位数组,可以想到容量应该是从大到小枚举的)

优化后的代码

cpp

// 40 = 2x4x5 ->  此时需要求8 由 [5] 以内的元素组合完成的数量
#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
typedef long long ll;
const int maxn = 1e5;

int n;
const ll mod = 998244353;
ll t;

ll ans;
ll f[2][10000+5]; //上限数字1000
std::vector<ll> fac;

//得到所有的因子
void get_fac() {
    fac.clear();
    fac.push_back(1); // 因子1
    for(ll i = 2;i*i <= t ;++i ) // i: 2->t
    {
        if( t % i == 0)  {
            fac.push_back(i);
            if( t / i != i)  //放置放两遍
                fac.push_back(t / i);
        }

    }

    std::sort(fac.begin(),fac.end());
    fac.push_back(t);
    // for(auto v: fac) std::cout << v << " ";
    // std::cout  << "\n";
}

void dp() {
    memset(f,0,sizeof(f));
    f[0][0] = 1;

    //枚举物品
    int pre  =0;
    int now;

    // k =1 ,表示不从因子 1 开始
    for(int k = 1 ;k<fac.size(); k++)
    {
        int i = k+1;
        now = pre^1;
        //枚举容量
        for(int j = 0 ;j < fac.size();j++) {
            f[now][j] = f[pre][j];
            auto V = fac[j]; // 容量
            if( V >= fac[k] && V % fac[k]== 0) {
                //使用这个物品
                int pos = std::lower_bound(fac.begin(),fac.end(),V / fac[k]) - fac.begin();
                f[now][j] += f[pre][pos];
                f[now][j] %= mod;
            }
        }

        // std::cout << i << ": ";
        // for(int j = 0 ;j < fac.size();j++) 
        //     std::cout << f[now][j] << " ";
        // std::cout  << "\n";
        pre^=1;
    }
    
    // std::cout << (f[now][fac.size()-1] ) << std::endl;
    std::cout << (f[now][fac.size()-1] - 1) % mod << "\n";

}

int main (int argc, char *argv[]) {
    int T;
    std::cin >> T;
    while (T--) {
        std::cin >> t;
        get_fac();
        dp();
        
    }
    
    return 0;
}

拆分

目录

优化

1. 什么是“因子最多”的数？

优化后的代码