CCF-CSP认证考试 202312-2 因子化简 100分题解

更多 CSP 认证考试题目题解可以前往：CCF-CSP 认证考试真题题解

---

原题链接： 202312-2 因子化简

时间限制： 2.0s
内存限制： 512.0MB

题目背景

质数（又称“素数”）是指在大于 $1$ 的自然数中，除了 $1$ 和它本身以外不再有其他因数的自然数。

问题描述

小 P 同学在学习了素数的概念后得知，任意的正整数 $n$ 都可以唯一地表示为若干素因子相乘的形式。如果正整数 $n$ 有 $m$ 个不同的素数因子 $p_1,p_2,\cdots ,p_m$，则可以表示为：$n=p_1^{t_1}\times p_2^{t_2}\times \cdots \times p_m^{t_m}$。

小 P 认为，每个素因子对应的指数 $t_i$ 反映了该素因子对于 $n$ 的重要程度。现设定一个阈值 $k$，如果某个素因子 $p_i$ 对应的指数 $t_i$ 小于 $k$，则认为该素因子不重要，可以将 $p_i^{t_i}$ 项从 $n$ 中除去；反之则将 $p_i^{t_i}$ 项保留。最终剩余项的乘积就是 $n$ 简化后的值，如果没有剩余项则认为简化后的值等于 $1$。

试编写程序处理 $q$ 个查询：

每个查询包含两个正整数 $n$ 和 $k$，要求计算按上述方法将 $n$ 简化后的值。

输入格式

从标准输入读入数据。

输入共 $q+1$ 行。

输入第一行包含一个正整数 $q$，表示查询的个数。

接下来 $q$ 行每行包含两个正整数 $n$ 和 $k$，表示一个查询。

输出格式

输出到标准输出。

输出共 $q$ 行。

每行输出一个正整数，表示对应查询的结果。

样例输入

3
2155895064 3
2 2
10000000000 10

样例输出

2238728
1
10000000000

样例解释

查询一：

$n=2^3\times 3^2\times 23^4\times 107$

其中素因子 $3$ 指数为 $2$，$107$ 指数为 $1$。将这两项从 $n$ 中除去后，剩余项的乘积为 $2^3\times 23^4=2238728$。

查询二：

所有项均被除去，输出 $1$。

查询三：

所有项均保留，将 $n$ 原样输出。

子任务

$40\%$ 的测试数据满足：$n\le 1000$；

$80\%$ 的测试数据满足：$n\le 10^5$；

全部的测试数据满足：$1<n\le 10^{10}$ 且 $1<k,q\le 10$。

---

题解

直接进行质因数分解，分解成为 $n=p_1^{t_1}\times p_2^{t_2}\times \cdots \times p_k^{t_k}$ 的形式。

由于因子是成对出现，如果 $a\ge \sqrt{n}$ 是 $n$ 的因子，则必存在 $b=\frac{n}{a}\le \sqrt{n}$ 也是 $n$ 的因子，所以只需枚举 $1\sim \sqrt{n}$ 内的数，判断是否是为因数即可。在从小到大枚举的过程中，如果找到一个因子 $i$，就将 $n$ 的所有因子 $i$ 全部除掉，按照此过程找出来的必然全是质因数，即可在 $\mathcal{O}(\sqrt{n})$ 的时间内对一个数完成分解。

然后判断 $t_i$ 是否大于 $k$，决定答案中是否要保留这个质因子的幂。

注意 $n$ 的范围是 $n\le 10^{10}$，需要开 long long。

时间复杂度：$\mathcal{O}(T\sqrt{n})$。

参考代码（15ms，2.925MB）

/*
    Created by Pujx on 2024/2/2.
*/
#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
//#define int long long
//#define double long double
using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
#define inf (int)0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define yn(x) cout << (x ? "yes" : "no") << endl
#define Yn(x) cout << (x ? "Yes" : "No") << endl
#define YN(x) cout << (x ? "YES" : "NO") << endl
#define mem(x, i) memset(x, i, sizeof(x))
#define cinarr(a, n) for (int i = 1; i <= n; i++) cin >> a[i]
#define cinstl(a) for (auto& x : a) cin >> x;
#define coutarr(a, n) for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n]
#define coutstl(a) for (const auto& x : a) cout << x << ' '; cout << endl
#define all(x) (x).begin(), (x).end()
#define md(x) (((x) % mod + mod) % mod)
#define ls (s << 1)
#define rs (s << 1 | 1)
#define ft first
#define se second
#define pii pair<int, int>
#ifdef DEBUG
    #include ""
#else
    #define dbg(...) void(0)
#endif

const int N = 2e5 + 5;
//const int M = 1e5 + 5;
const int mod = 998244353;
//const int mod = 1e9 + 7;
//template <typename T> T ksm(T a, i64 b) { T ans = 1; for (; b; a = 1ll * a * a, b >>= 1) if (b & 1) ans = 1ll * ans * a; return ans; }
//template <typename T> T ksm(T a, i64 b, T m = mod) { T ans = 1; for (; b; a = 1ll * a * a % m, b >>= 1) if (b & 1) ans = 1ll * ans * a % m; return ans; }

int a[N];
i64 n, m, t, k, q;

void work() {
    cin >> n >> k;
    i64 ans = 1;
    for (int i = 2; 1ll * i * i <= n; i++)
        if (n % i == 0) {
            int cnt = 0;
            while (n % i == 0) n /= i, cnt++;
            if (cnt >= k) while (cnt--) ans *= i;
        }
    if (k == 1) ans *= n;
    cout << ans << endl;
}

signed main() {
#ifdef LOCAL
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\", "r", stdin);
    freopen("C:\\Users\\admin\\CLionProjects\\Practice\\", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    cin >> Case;
    while (Case--) work();
    return 0;
}
/*
     _____   _   _       _  __    __
    |  _  \ | | | |     | | \ \  / /
    | |_| | | | | |     | |  \ \/ /
    |  ___/ | | | |  _  | |   }  {
    | |     | |_| | | |_| |  / /\ \
    |_|     \_____/ \_____/ /_/  \_\
*/

关于代码的亿点点说明：

1. 代码的主体部分位于 void work() 函数中，另外会有部分变量申明、结构体定义、函数定义在上方。
2. #pragma ... 是用来开启 O2、O3 等优化加快代码速度。
3. 中间一大堆 #define ... 是我习惯上的一些宏定义，用来加快代码编写的速度。
4. "" 头文件是我用于调试输出的代码，没有这个头文件也可以正常运行（前提是没定义 DEBUG 宏），在程序中如果看到 dbg(...) 是我中途调试的输出的语句，可能没删干净，但是没有提交上去没有任何影响。
5. ios::sync_with_stdio(false); (0); (0); 这三句话是用于解除流同步，加快输入 cin 输出 cout 速度（这个输入输出流的速度很慢）。在小数据量无所谓，但是在比较大的读入时建议加这句话，避免读入输出超时。如果记不下来可以换用 scanf 和 printf，但使用了这句话后，cin 和 scanf、cout 和 printf 不能混用。
6. 将 main 函数和 work 函数分开写纯属个人习惯，主要是为了多组数据。