CCF CSP题解：因子化简（202312-2）

本文主要是介绍CCF CSP题解：因子化简（202312-2），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接和思路

OJ链接：传送门。

问题重述

本题基于一个基本事实，即任何一个大整数 $n$ 都可以唯一地分解为如下形式
$p_1^{t_1} \times p_2^{t_2} \times \cdots \times p_m^{t_m}$ 其中， $p_1, p_2, \cdots, p_m$ 表示 $m$ 个素因子，素因子上的幂 $t_i > 0 (1 \le i \le m)$ 。

本题给出 $q$ 组 $n, k$ ，满足 $\le 10^{10}, 1 < k, q \le 10$ ，要求对每组 $n, k$ ，求出 $n$ 除以所有满足 $t_i<k$ 的 $p_i^{t_i}$ 后的结果，即求出
$\frac{n}{\prod_{1 \le i \le m 且 t_i<k}p_i^{t_i}} = \prod_{1 \le i \le m 且 t_i \ge k}p_i^{t_i}$

求解思路

由于 $n$ 较大，求出小于 $n$ 的所有的素数是很困难的。因此，我们考虑使用素数筛先求出 $10^5$ 以内的所有素数。如果出现有 $p_i>10^5$ 的情况，则对应的 $t_i$ 必不可能大于1，只能等于1，且这样的 $p_i$ 最多只可能有1个。常见的素数筛有埃氏筛、欧拉筛等。本文使用埃氏筛，其实现如下：

static vector<long long> primes;
// 埃拉托斯特尼筛法，时间复杂度为O(n * loglogn)
void Find_Prime_number(long long n = N){vector<bool> flag(n + 1, true);//0和1不是素数，直接初始化好flag[0] = 0;flag[1] = 0;//从2开始，1不是素数for (long long i = 2; i <= n; i++){//如果当前数字是素数if (flag[i]){//i的倍数标记被不是素数for (long long j = i * i; j <= n; j += i)flag[j] = false;primes.push_back(i);}}
}

我们将素数筛获得的所有的 $10^5$ 以内的素数保存在vector<long long> primes中。然后，将 $n$ 依次尝试除以primes中的每个质因子 $p_i$ 。如果能够整除 $p_i$ 的次数大于等于 $k$ ，则说明 $p_i$ 是“重要的”，因此恢复到尝试除以 $p_i$ 之前的值。遍历完primes后，我们再处理可能存在的大于 $10^5$ 的质因子。

上文提到，如果存在 $p_i > 10^5$ ，在本题的设定中，最多只可能有1个，且对应的 $t_i$ 只可能为1，由于 $k>1=t_i$ ，最终答案要剔除掉 $p_i ^{t_i}$ 。

因此，我们需要引入如下函数，用以辅助判断 $n$ 除以 $\prod_{1 \le i \le m 且 p_i \le 10^5}p_i^{t_i}$ 后，是否是一个大于 $10^5$ 素数。如果是，最终结果应该除以这个素数。

bool is_prime(long long n){for (long long i = 2; i * i <= n; i++)if(n % i == 0)return false;return true;
}

AC代码

满分代码如下，使用CPP 11标准即可编译运行。
在这里插入图片描述

#include <iostream>
#include <vector>
using namespace std;const long long N = 1e5+5;static vector<long long> primes;// 埃拉托斯特尼筛法，时间复杂度为O(n * loglogn)
void Find_Prime_number(long long n = N){vector<bool> flag(n + 1, true);//0和1不是素数，直接初始化好flag[0] = 0;flag[1] = 0;//从2开始，1不是素数for (long long i = 2; i <= n; i++){//如果当前数字是素数if (flag[i]){//i的倍数标记被不是素数for (long long j = i * i; j <= n; j += i)flag[j] = false;primes.push_back(i);}}
}bool is_prime(long long n){for (long long i = 2; i * i <= n; i++)if(n % i == 0)return false;return true;
}int main() {Find_Prime_number();int q;cin >> q;while(q--) {long long  n;int k;cin >> n >> k;long long flag = n;for (long long prime: primes) {long long tmp = n;int cnt = 0;while (n % prime == 0){n /= prime;flag /= prime;cnt++;}if (cnt >= k)   // 如果t_i足够大，说明不需要除以p_in = tmp;    // 恢复}if (flag > N && is_prime(flag)){// 如果存在大于N的质因子p_i，其对应的t_i=1<k，需要去除n /= flag;}cout << n << endl;}return 0;
}