因子化简

GitHub跳转原题关系图Canvas 关系图返回列表

试除分解每个 n，统计各质因子的指数，只保留指数不小于阈值 k 的完整质因数幂。

OJ: shumeng

题目 ID: CSP202312B

难度:普及-

标签:数论质因数分解枚举

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 试除并统计指数
    2. 按阈值决定去留
    3. 处理剩余的大质因子
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

对正整数 nn 做质因数分解，得到 n=p1t1×⋯×pmtmn=p_1^{t_1}\times\cdots\times p_m^{t_m}。给定阈值 kk，指数 ti<kt_i<k 的质因数幂整体删除，指数 ti≥kt_i\ge k 的完整保留；若全部删除则结果为 11。处理 qq 组查询，每组给出 n,kn,k 输出简化后的值。

思路

直接在 nn 上做试除分解即可。

试除并统计指数

从 22 开始枚举可能的质因子 prime。当 value % prime == 0 时不断除去它并统计指数 exponent，直到除尽；这样既完成了分解，也拿到了该质因子的完整次数。

按阈值决定去留

  • 若 exponent >= k，把 prime^exponent 完整乘入答案；
  • 否则忽略这一整项。

这里必须先完整统计一个质因子的指数，再决定是否乘回，不能一边除一边乘。

处理剩余的大质因子

试除循环只枚举到 value\sqrt{value}。结束后如果 value > 1，它必然是一个指数为 11 的大质因子。由于本题保证 k>1k>1，它不会被保留；代码保留了 k<=1 时的通用处理作为兜底。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:40
 */
#include <bits/stdc++.h>
using namespace std;

// 对 n 做试除分解，只保留指数不小于 k 的质因数幂
long long simplify(long long n, long long k) {
    long long value = n;
    long long answer = 1;
    for (long long prime = 2; prime * prime <= value; prime++) {
        if (value % prime != 0) continue;
        // 统计 prime 在 value 中的指数
        long long exponent = 0;
        while (value % prime == 0) {
            value /= prime;
            exponent++;
        }
        // 指数不小于 k 才保留完整的 prime^exponent
        if (exponent >= k) {
            for (long long i = 0; i < exponent; i++) answer *= prime;
        }
    }
    // 试除结束后若剩余 value > 1，它是指数为 1 的质因子；
    // 本题 k>1 所以不会被保留，这里保留 k<=1 时的通用处理
    if (value > 1 && k <= 1) answer *= value;
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;
    while (q--) {
        long long n, k;
        cin >> n >> k;
        cout << simplify(n, k) << '\n';
    }

    return 0;
}

复杂度

单次查询最多试除到 n\sqrt n，时间复杂度为 O(n)O(\sqrt n)，空间复杂度为 O(1)O(1)；全部查询为 O(qn)O(q\sqrt n)。

总结

因子是否保留只取决于它的指数，必须先统计完整次数再决定去留。试除结束后剩余的大质因子只能出现一次，指数判断是本题容易遗漏的边界。