CCF-CSP 202312-2 因子化简（Java、C++、Python）

文章目录

• 因子化简
• • 题目背景
  • 问题描述
  • 输入格式
  • 输出格式
  • 样例输入
  • 样例输出
  • 样例解释
  • 子任务
• 满分代码
• • Java
  • C++
  • Python
  • 线性筛法

因子化简

题目背景

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

问题描述

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

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

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

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

输入格式

从标准输入读入数据。

输入共 q + 1 q+1 q+1 行。

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

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

输出格式

输出到标准输出。

输出共 q q q 行。

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

样例输入

3 2155895064 3 2 2 10000000000 10

• 1
• 2
• 3
• 4

样例输出

2238728 1 10000000000

• 1
• 2
• 3

样例解释

查询一：

• n = 2 3 × 3 2 × 2 3 4 × 107 n=2^3\times3^2\times23^4\times107 n=23×32×234×107
• 其中素因子 3 指数为 2, 107 指数为 1。将这两项从 n n n 中除去后，剩余项的乘积为 2 3 × 2 3 4 = 2238728 2^3\times23^4=2238728 23×234=2238728。

查询二：

• 所有项均被除去。输出 1。

查询三：

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

子任务

40% 的测试数据满足： n ≤ 1000 n\leq1000 n≤1000；

80% 的测试数据满足： n ≤ 1 0 5 n\leq10^5 n≤105；

全部的测试数据满足 : 1 < n ≤ 1 0 10 :1:1<n≤1010 且 1 < k , q ≤ 10 11<k,q≤10。

满分代码

注意到： 对于 n n n，仅有一个最大素因子 m m m 可能大于 n \sqrt n n ​，也就是说我们只需要除去 2 ∼ n 2 \sim \sqrt n 2∼n ​ 的素因子就可以得到 m m m，所以对于全部数据 n ≤ 1 0 10 n \leq 10^{10} n≤1010，我们只需要求出 2 ∼ 1 0 5 2 \sim 10^5 2∼105 中所有质数即可，直接用试除法，稍微优化一下时间复杂度也就 1 0 7 10^7 107，可以通过，如果数据 n ≤ 1 0 14 n\leq10^{14} n≤1014 就需要使用线性筛法了。

Java

import java.util.*; import java.io.*; public class Main { static QuickInput in = new QuickInput(); static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out))); static int max = 100007; public static void main(String[] args) throws IOException { long q = in.nextLong(); List<Integer> list = new ArrayList<>(); for (int i = 2; i < max; i++) check(i, list); for (int i = 0; i < q; i++) { long n = in.nextLong(), k = in.nextLong(); long ans = n; int[] cnt = new int[max]; for (int j : list) { if (n == 1) break; while (n % j == 0) { n /= j; cnt[j]++; } } ans /= n; for (int j = 0; j < max; j++) { if (cnt[j] < k && cnt[j] != 0) { ans /= Math.pow(j, cnt[j]); } } out.println(ans); } out.flush(); } static void check(int n, List<Integer> list) { for (int i : list) { if (i * i > n) break; if (n % i == 0) return; } list.add(n); } static class QuickInput { StreamTokenizer input = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); long nextLong() throws IOException { input.nextToken(); return (long) input.nval; } } }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52

C++

#include using namespace std; const int max_val = 1e5; void check(int n, vector<int>& list) { for (int i : list) { if (i * i > n) break; if (n % i == 0) return; } list.push_back(n); } int main() { ios::sync_with_stdio(false); cin.tie(0); int max = max_val; long long q; cin >> q; vector<int> primeList; for (int i = 2; i < max; i++) { check(i, primeList); } for (int i = 0; i < q; i++) { long long n, k; cin >> n >> k; long long ans = n; vector<int> cnt(max_val, 0); for (int j : primeList) { if (n == 1) break; while (n % j == 0) { n /= j; cnt[j]++; } } ans /= n; for (int j = 0; j < max_val; j++) { if (cnt[j] < k && cnt[j] != 0) { ans /= pow(j, cnt[j]); } } cout << ans << endl; } return 0; }

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52

Python

max_val = 100000 primes = [] for i in range(2, max_val): if all(i % p != 0 for p in primes if p * p <= i): primes.append(i) q = int(input()) for _ in range(q): n, k = map(int, input().split()) ans = n cnt = [0] * max_val for prime in primes: while n % prime == 0: n //= prime cnt[prime] += 1 ans //= n for prime, t in enumerate(cnt): if t < k and t != 0: ans //= pow(prime, t) print(ans)

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22

线性筛法

max_val = 100000 is_prime = [True] * (max_val + 1) primes = [] for i in range(2, max_val + 1): if is_prime[i]: primes.append(i) for j in range(len(primes)): if i * primes[j] > max_val: break is_prime[i * primes[j]] = False if i % primes[j] == 0: break

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15