一、小节概述

递推与递归是计算机科学的基石，贯穿于动态规划、分治、回溯等高级算法中，是解决复杂问题的基本方法论。

学习目标：

1. 理解递推与递归的基本概念与区别
2. 掌握常见递归模型的实现与优化
3. 能够将递归问题转化为递推求解
4. 熟练运用递归解决排列组合、搜索等问题
5. 理解递归与动态规划的内在联系

建议学时：6~8h

二、核心概念辨析

1. 递推（Iteration）

定义：从已知的初始条件出发，通过递推关系式逐步推导出后续结果的计算过程。 特点：

• 自底向上：从基本情况开始，逐步构建复杂情况
• 迭代实现：通常使用循环结构
• 空间效率高：通常只需存储有限状态
• 时间复杂度明确：通常易于分析

2. 递归（Recursion）

定义：函数直接或间接调用自身来解决问题的方法。 特点：

• 自顶向下：从问题本身出发，分解为子问题
• 简洁优雅：代码结构清晰，接近数学定义
• 系统栈开销：递归深度受栈空间限制
• 可能重复计算：需要优化（记忆化搜索）

3. 递推与递归的关系

• 递归是描述，递推是计算：递归描述问题分解关系，递推实现具体计算
• 互为转化：多数递归问题可以转化为递推求解（动态规划）
• 选择原则：
  • 问题有明显递推关系 → 使用递推
  • 问题有自然递归结构 → 使用递归
  • 递归深度过大 → 考虑递推或优化

三、递归基础

1. 递归三要素

// 1. 递归终止条件（Base Case）
if (问题足够小，可直接求解) {
    return 基本解;
}

// 2. 递归调用（Recursive Call）
子问题结果 = 递归函数(缩小规模的问题);

// 3. 结果合并（Combine Results）
return 合并(子问题结果, 当前问题处理);

2. 递归实现要点

// 递归函数模板
返回类型 递归函数(参数) {
    // 1. 递归终止条件
    if (终止条件满足) {
        return 基本结果;
    }

    // 2. 预处理（可选）
    预处理当前状态();

    // 3. 递归调用
    结果类型 res = 初始值;
    for (所有可能的分解方式) {
        子问题结果 = 递归函数(缩小后的参数);
        res = 合并(res, 子问题结果);
    }

    // 4. 后处理（可选）
    后处理当前状态();

    return res;
}

3. 递归树分析

递归树是分析递归算法复杂度的有效工具：

• 节点：表示一次递归调用
• 边：表示递归调用关系
• 深度：递归调用栈的最大深度
• 节点数：总递归调用次数

示例：斐波那契数列递归树

               fib(4)
              /      \
          fib(3)     fib(2)
         /      \    /    \
     fib(2) fib(1) fib(1) fib(0)
     /    \
 fib(1) fib(0)

四、经典递归模型

1. 斐波那契数列

问题描述：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n≥2)

// 朴素递归（指数复杂度）
int fib_recursive(int n) {
    if (n <= 1) return n;
    return fib_recursive(n-1) + fib_recursive(n-2);
}

// 递推实现（线性复杂度）
int fib_iterative(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

// * 矩阵快速幂（对数复杂度） *了解即可*
struct Matrix {
    long long a[2][2];
    Matrix() { memset(a, 0, sizeof(a)); }
    Matrix operator*(const Matrix& other) const {
        Matrix res;
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k < 2; k++)
                    res.a[i][j] += a[i][k] * other.a[k][j];
        return res;
    }
};

Matrix matrix_pow(Matrix m, int n) {
    Matrix res;
    res.a[0][0] = res.a[1][1] = 1;  // 单位矩阵
    while (n) {
        if (n & 1) res = res * m;
        m = m * m;
        n >>= 1;
    }
    return res;
}

int fib_matrix(int n) {
    if (n <= 1) return n;
    Matrix m;
    m.a[0][0] = m.a[0][1] = m.a[1][0] = 1;
    Matrix res = matrix_pow(m, n - 1);
    return res.a[0][0];
}

2. 汉诺塔问题

问题描述：将n个盘子从A柱移动到C柱，每次只能移动一个盘子，且大盘不能在小盘上面。

void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        cout << "Move disk 1 from " << from << " to " << to << endl;
        return;
    }
    // 1. 将n-1个盘子从from移动到aux（借助to）
    hanoi(n-1, from, aux, to);
    // 2. 将第n个盘子从from移动到to
    cout << "Move disk " << n << " from " << from << " to " << to << endl;
    // 3. 将n-1个盘子从aux移动到to（借助from）
    hanoi(n-1, aux, to, from);
}

// 移动次数：H(n) = 2*H(n-1) + 1 = 2^n - 1

五、递归优化技术

1. 记忆化搜索（Memoization）

核心思想：保存已计算的结果，避免重复计算。

// 斐波那契数列记忆化搜索
vector<int> memo(100, -1);  // -1表示未计算

int fib_memo(int n) {
    if (n <= 1) return n;

    // 如果已经计算过，直接返回
    if (memo[n] != -1) return memo[n];

    // 计算并保存结果
    memo[n] = fib_memo(n-1) + fib_memo(n-2);
    return memo[n];
}

// 更通用的记忆化搜索模板，借助map记录
unordered_map<string, 返回类型> memo_map;

返回类型 递归函数带记忆化(参数) {
    // 生成唯一键
    string key = 参数序列化();
    // 检查是否已计算
    if (memo_map.find(key) != memo_map.end()) {
        return memo_map[key];
    }
    // 计算并保存
    返回类型 result = 递归计算(参数);
    memo_map[key] = result;
    return result;
}

2. 尾递归优化（Tail Recursion）

定义：递归调用是函数体中最后执行的操作，且返回值就是递归调用的结果。 特点：编译器可以优化为循环，避免栈溢出。

// 普通递归（非尾递归）
int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n-1);  // 需要等待递归结果进行乘法
}

// 尾递归形式
int factorial_tail(int n, int acc = 1) {
    if (n == 0) return acc;
    return factorial_tail(n-1, n * acc);  // 递归调用是最后操作
}

// 优化后的等价循环
int factorial_loop(int n) {
    int acc = 1;
    for (int i = 1; i <= n; i++) {
        acc *= i;
    }
    return acc;
}

3. 递归改递推（动态规划）

核心思想：使用数组存储子问题结果，从基础情况开始逐步计算。

// 斐波那契数列：递归 → 递推
int fib_dp(int n) {
    if (n <= 1) return n;

    vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[n];
}

// 滚动数组空间优化：只保留必要状态
int fib_dp_optimized(int n) {
    if (n <= 1) return n;

    int prev2 = 0;  // F(i-2)
    int prev1 = 1;  // F(i-1)

    for (int i = 2; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

六、递推算法

1. 线性递推

形式：F(n) = a₁F(n-1) + a₂F(n-2) + ... + aₖF(n-k) + g(n)

// 求解线性递推的一般方法
vector<int> linear_recurrence(int n, int k, vector<int>& a, vector<int>& init) {
    if (n < k) return init[n];

    vector<int> dp(n + 1);
    for (int i = 0; i < k; i++) {
        dp[i] = init[i];
    }

    for (int i = k; i <= n; i++) {
        dp[i] = 0;
        for (int j = 1; j <= k; j++) {
            dp[i] += a[j-1] * dp[i-j];
        }
        // 如果包含非齐次项 g(n)
        // dp[i] += g(i);
    }

    return dp;
}

2. 二维递推

典型问题：杨辉三角、网格路径

// 杨辉三角递推【数字三角形】
vector<vector<int>> pascal_triangle(int n) {
    vector<vector<int>> triangle(n);
    for (int i = 0; i < n; i++) {
        triangle[i].resize(i + 1);
        triangle[i][0] = triangle[i][i] = 1;
        for (int j = 1; j < i; j++) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
        }
    }
    return triangle;
}

// 网格路径问题（从左上到右下，只能向右或向下）
int grid_paths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 0));

    // 初始化第一行和第一列
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;

    // 递推计算
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

    return dp[m-1][n-1];
}

七、递归与回溯

1. 回溯算法框架

void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        结果集.add(路径);
        处理结果;
        return;
    }

    for (选择 in 选择列表) {
        // 做选择
        路径.add(选择);
        修改选择列表;

        // 递归进入下一层
        backtrack(路径, 选择列表);

        // 撤销选择（回溯）
        路径.remove(选择);
        恢复选择列表;
    }
}

2. 经典回溯问题

2.1 N皇后问题

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<string> board(n, string(n, '.'));
    vector<bool> col(n, false);      // 列占用标记
    vector<bool> diag1(2*n-1, false); // 主对角线
    vector<bool> diag2(2*n-1, false); // 副对角线

    function<void(int)> backtrack = [&](int row) {
        if (row == n) {
            res.push_back(board);
            return;
        }

        for (int c = 0; c < n; c++) {
            int d1 = row + c;          // 主对角线索引
            int d2 = row - c + n - 1;  // 副对角线索引

            if (!col[c] && !diag1[d1] && !diag2[d2]) {
                // 放置皇后
                board[row][c] = 'Q';
                col[c] = diag1[d1] = diag2[d2] = true;

                // 递归下一行
                backtrack(row + 1);

                // 回溯
                board[row][c] = '.';
                col[c] = diag1[d1] = diag2[d2] = false;
            }
        }
    };

    backtrack(0);
    return res;
}

2.2 解数独

bool solveSudoku(vector<vector<char>>& board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') {
                for (char c = '1'; c <= '9'; c++) {
                    if (isValid(board, i, j, c)) {
                        board[i][j] = c;
                        if (solveSudoku(board)) return true;
                        board[i][j] = '.';  // 回溯
                    }
                }
                return false;  // 所有数字尝试失败
            }
        }
    }
    return true;  // 所有格子已填满
}

八、递归与分治

1. 分治算法框架

返回类型 分治函数(问题P) {
    if (问题P的规模足够小) {
        return 直接求解(P);
    }

    // 分解：将P分解为子问题P₁, P₂, ..., Pₖ
    vector<子问题> subproblems = 分解(P);

    // 解决：递归解决子问题
    vector<结果> subresults;
    for (auto& sub : subproblems) {
        subresults.push_back(分治函数(sub));
    }

    // 合并：合并子问题的解
    return 合并(subresults);
}

2. 经典分治算法

2.1 归并排序

void merge_sort(int q[], int l, int r) {
    if (l >= r) return;  // 只有一个元素
    int mid = (l + r) / 2;
    merge_sort(q, l, mid);
    merge_sort(q, mid+1, r);
    // 归并操作
    int k = 0, i = l, j = mid+1;
    while (i <= mid && j <= r) {
        if (q[i] <= q[j]) {
            temp[k] = q[i];
            k++; i++;
        }
        else {
            temp[k] = q[j];
            k++; j++;
        }
    }
    while (i <= mid) temp[k++] = q[i++];
    while (j <= r) temp[k++] = q[j++];
    for(int i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];
}

2.2 快速排序

void quick_sort(int l, int r, vector<int> &a) {
    if(l >= r) return;
    int x = a[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j) {
        do i ++; while(a[i] < x);
        do j --; while(a[j] > x);
        if(i < j) swap(a[i], a[j]);
    }
    if(k <= j) quick_sort(l, j, a);
    else quick_sort(j + 1, r, a);
}

经典例题

例题1：递归实现指数型枚举

题目描述：从 1∼n 这 n (1 ≤ n ≤ 15) 个整数中随机选取任意多个，输出所有可能的选择方案。

思路：

1. 递归搜索：每个数字有两种状态：选或不选
2. 状态表示：使用数组记录每个数字的选择状态
3. 递归设计：
   • 递归参数：当前正在考虑的数字 u
   • 递归边界：u > n 时输出当前方案
   • 递归过程：对数字 u，先尝试不选，再尝试选
4. 升序输出：由于递归是按数字顺序进行的，自然满足升序要求

代码实现1：

int n;
vector<int> chosen;  // 存储当前选择的数字
void dfs(int u) {
    if (u > n) {
        // 输出当前方案
        for (int i = 0; i < chosen.size(); i++) {
            cout << chosen[i];
            if (i < chosen.size() - 1) cout << " ";
        }
        cout << endl;
        return;
    }
    // 不选数字 u
    dfs(u + 1);
    // 选数字 u
    chosen.push_back(u);
    dfs(u + 1);
    chosen.pop_back();  // 回溯
}

int main() {
    cin >> n;
    dfs(1);
    return 0;
}

代码实现2：状态压缩

int n;
void dfs(int u, int state){
    if (u == n){
        for (int i = 0; i < n; i++){
            if (state >> i & 1) cout << i + 1 << " ";
        }
        cout << endl;
        return;
    }
    dfs(u + 1, state) // 不选
    dfs(u + 1, state | 1 << u); // 选
}
dfs(0, 0);

时间复杂度：O(2^n)，总共有 2^n 个子集 空间复杂度：O(n)，递归栈深度为 n

例题2：递归实现组合型枚举

题目描述：从 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。n, m (1 ≤ m ≤ n ≤ 20)

思路：

1. 组合与排列的区别：组合不考虑顺序，排列考虑顺序
2. 递归剪枝：当已选数字数量超过 m 或剩余数字不足以凑齐 m 个时提前返回
3. 避免重复：按升序选择数字，每次从比上一个数字大的位置开始选
4. 递归设计：
   • 参数：当前正在考虑的数字 u，已选数字数量 cnt
   • 边界：cnt == m 时输出方案
   • 剪枝：cnt > m 或 cnt + (n-u+1) < m 时返回

代码实现1：

int n, m;
vector<int> chosen;

void dfs(int u, int cnt) {
    // 剪枝：已选数量超过 m 或剩余数字不够
    if (cnt > m || cnt + (n - u + 1) < m) return;

    if (u > n) {
        if (cnt == m) {
            for (int i = 0; i < chosen.size(); i++) {
                cout << chosen[i];
                if (i < chosen.size() - 1) cout << " ";
            }
            cout << endl;
        }
        return;
    }
    // 不选数字 u
    dfs(u + 1, cnt);
    // 选数字 u
    chosen.push_back(u);
    dfs(u + 1, cnt + 1);
    chosen.pop_back();
}

代码实现2：

int n, m;
void dfs(int u, int cnt, int state){
    if (cnt > m || cnt + n - u < m) continue;
    if (cnt == m){
        for (int i = 0; i < n; i++){
            if (state >> i & 1) cout << i + 1 << " ";
        }
        cout << endl;
        return;
    }
    dfs(u + 1, cnt, state) // 不选
    dfs(u + 1, cnt + 1, state | 1 << u); // 选
}

时间复杂度：O(C(n, m) × m)，C(n, m) 是组合数 空间复杂度：O(m)，递归栈深度为 m

例题3：递归实现排列型枚举

题目描述：把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。

思路：

1. 排列与组合的区别：排列考虑顺序，组合不考虑顺序
2. 回溯算法：依次确定每个位置放哪个数字
3. 标记数组：记录哪些数字已经被使用
4. 递归设计：
   • 参数：当前正在填充的位置 u
   • 边界：u > n 时输出排列
   • 过程：遍历所有未使用的数字，放入当前位置

代码实现1：

int n;
vector<int> permutation;  // 当前排列
vector<bool> used;        // 标记数组，记录数字是否已使用

void dfs(int u) {
    if (u > n) {
        for (int i = 0; i < n; i++) {
            cout << permutation[i] << " ";
        }
        cout << endl;
        return;
    }

    // 尝试将每个未使用的数字放入位置 u
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            used[i] = true;
            permutation.push_back(i);
            dfs(u + 1);
            permutation.pop_back();
            used[i] = false;
        }
    }
}
dfs(1);

代码实现2：

vector<int> ans;
int n;
void dfs(int state){
    if (ans.size() == n){
        for (int i : ans) cout << i << " ";
        cout << endl;
        return;
    }
    for (int i = 0; i < n; i++){
        if (!(state >> i & 1)){
            ans.push_back(i+1);
            dfs(state | 1 << i);
            ans.pop_back();
        }
    }
}
dfs(0);

时间复杂度：O(n × n!)，总共有 n! 个排列，每个排列输出需要 O(n) 空间复杂度：O(n)，递归栈深度为 n

例题4：费解的开关

题目描述：有一个 5×5 的 01 矩阵，点击任意一个位置，该位置以及上下左右四个相邻位置（如果存在）的数字都会翻转（0变1，1变0）。求最少需要点击多少次才能将矩阵全部变为1。

输入格式：

• 第一行：整数 n (n ≤ 500)，表示测试数据组数
• 每组数据：5行，每行5个字符（'0'或'1'），表示初始矩阵

输出格式：每组数据输出一个整数，表示最少点击次数。如果6步以内无法使矩阵全为1，输出-1。

思路：

1. 开关操作的本质

• 二性性 ：每个开关按两次等于没按，按三次等于按一次。所以每个位置的操作状态只有 （不按）和 （按）。
• 无序性 ：最终结果只取决于哪些开关被按下，而与按下的先后顺序无关。

2. 局部确定性与递推

• 唯一约束 ：如果上一行的灯是灭的，唯一能把它点亮且不破坏更上方行的方法，就是按下它正下方的开关。
• 连锁反应 ：第一行的状态一旦固定，后面所有行的操作都是“被迫”产生的，这就是“以局部推全局”。

3. 状态压缩与位运算 (Bitmasking)

• 枚举全集 ：第一行有5列，共有$2^5$种操作可能。使用整数 0~31 的二进制位来代表“按”或“不按”。

4. 矩阵备份与恢复

• 为了尝试32种不同的第一行方案，每次枚举开始前必须用 memcpy 恢复原始数据。

---

代码实现：

#include <bits/stdc++.h>
#define ll long long

using namespace std;
char a[10][10], backup[10][10];
int dx[] = {0, 1, 0, -1, 0};
int dy[] = {1, 0, -1, 0, 0};

void click(int x, int y) { // 按下第x行第y列
    for (int i = 0; i < 5; i++) { // 自己，上下左右
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 1 && nx <= 5 && ny >= 1 && ny <= 5)
            a[nx][ny] ^= 1; // 48^1=49 49^1=48
    }
}

void solve() {
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; j++)
            cin >> a[i][j];
    memcpy(backup, a, sizeof a); // 将a备份到backup
    
    int ans = 10;
    
    // 枚举第一行按下开关的情况
    for (int i = 0; i < 32; i++) {
        int step = 0;
        memcpy(a, backup, sizeof backup);
        for (int j = 0; j < 5; j++) {
            if (i >> j & 1) { // 第一行的第j列按下了
                click(1, j + 1); // 模拟按下过程
                step ++;
            }
        }
        // 由当前第一行情况递推后面4行
        for (int r = 1; r < 5; r++) { // 行
            for (int c = 1; c <= 5; c++) { // 列
                if (a[r][c] == '0') {
                    click(r + 1, c);
                    step++;
                }
            }
        }
        // 检查第5行是否全亮
        bool ok = 1;
        for (int c = 1; c <= 5; c++)
            if (a[5][c] == '0') {
                ok = 0;
                break;
            }
        if (ok) ans = min(ans, step);
    }
    if (ans <= 6) cout << ans;
    else cout << -1;
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    while (n--) solve();
    return 0;
}

时间复杂度：O(32 × 5 × 5 × T) ≈ O(800T) 空间复杂度：O(1)

例题5：Strange Towers of Hanoi（四柱汉诺塔）

题目描述：在经典汉诺塔问题（三柱）的基础上增加一个柱子，求移动 n 个盘子的最少步数。

思路：

1. 经典汉诺塔：三柱汉诺塔的最少步数为 $H(n) = 2*H(n-1) + 1 = 2^n - 1$
2. 四柱汉诺塔：
   • 将 n 个盘子分成两部分：上面的 k 个盘子和下面的 n-k 个盘子
   • 步骤： a) 将上面的 k 个盘子移动到某一柱子（使用四柱） b) 将剩下的 n-k 个盘子移动到目标柱（使用三柱，因为有一个柱子被小盘子占用） c) 将 k 个盘子移动到目标柱（使用四柱）
3. 递推公式：设 F(n) 为四柱汉诺塔的最少步数
   • $F(n) = min_{1≤k<n} { 2×F(k) + H(n-k) }$
   • 其中 $H(m) = 2^m - 1$
4. 初始条件：$F(1) = 1$

代码实现：

const int N = 15;
const int INF = 0x3f3f3f3f;

int f[N];  // 四柱汉诺塔最少步数
int h[N];  // 三柱汉诺塔最少步数

void init() {
    // 计算三柱汉诺塔步数
    for (int i = 1; i < N; i++) {
        h[i] = (1 << i) - 1;  // 2^i - 1
    }

    // 计算四柱汉诺塔步数
    memset(f, 0x3f, sizeof f);
    f[1] = 1;

    for (int n = 2; n < N; n++) {
        for (int k = 1; k < n; k++) {
            f[n] = min(f[n], 2 * f[k] + h[n - k]);
        }
    }
}

时间复杂度：O(n²)，n ≤ 12 可忽略不计 空间复杂度：O(1)

例题6：Sumdiv（约数之和）

题目描述：求 A^B 的所有约数之和 mod 9901。 输入格式：一行两个整数 A, B (0 ≤ A, B ≤ 5×10^7) 输出格式：一个整数，表示 A^B 的约数之和 mod 9901

解题思路：

1. 约数之和公式：若 $n = p₁^c₁ × p₂^c₂ × ... × pₖ^cₖ$，则约数之和为：
   • $σ(n) = Π_{i=1}^k (1 + p_i + p_i² + ... + p_i^{c_i})$
2. A^B 的质因数分解：若 $A = p₁^c₁ × p₂^c₂ × ... × pₖ^cₖ$，则
   • $A^B = p₁^{c₁B} × p₂^{c₂B} × ... × pₖ^{cₖB}$
3. 等比数列求和：对于每个质因子 p，需要计算 $S(p, c) = 1 + p + p² + ... + p^c$ mod $9901$
4. 快速幂：计算 $p^i$ mod $9901$
5. 分治求等比数列和：
   • 若 c 为奇数：$S(p, c) = (1 + p^{(c+1)/2}) × S(p, (c-1)/2)$ mod 9901
   • 若 c 为偶数：$S(p, c) = (1 + p^{c/2}) × S(p, c/2-1) + p^c$ mod 9901

代码实现：

#include<bits/stdc++.h>
#define ll long long

using namespace std;

/*
s(p, k) = 
奇数：s(p, (k-1)/2) * (1+p^((k+1)/2))
偶数：s(p, (k-2)/2) * (1+p^(k/2)) + p^k

*/
const int Mod = 9901;
map<ll, ll> cnt; // cnt[i] = 3,  i^3

ll qmi(int a, int b){
    ll res = 1;
    while (b){
        if (b & 1) res = res * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return res;
}

ll s(ll p, ll k){ // 1+p+p^2+...+p^k 
    if (k == 0) return 1;
    if (k & 1){ // 奇数
        return s(p, (k-1)/2) * (1 + qmi(p, (k+1)/2)) % Mod;
    }
    else return (s(p, (k-2)/2) * (1+qmi(p, k/2)) % Mod + qmi(p, k)) % Mod;
}

int main()
{
    ll A, B;
    cin >> A >> B;
    if (A == 0){
        cout << 0;
        return 0;
    }
    int a = A; // a = 2
    for (int i = 2; i <= a / i; i++){
        while (a % i == 0){
            cnt[i] ++;
            a /= i;
        }
    }
    if (a > 1) cnt[a]++;
    
    ll res = 1;
    for (auto [key, val] : cnt) // 枚举型遍历
    {
        res = res * s(key, val * B) % Mod;
    }
    cout << res;
    
    return 0;
}

时间复杂度：O(√A + k log B)，k 为质因子个数 空间复杂度：O(k)

未完待续...