2024 ccfcsp认证打卡 2023 12-2 因子化简

屠苏之易，百里之峰

已于 2024-03-09 18:33:17 修改

阅读量331

点赞数 4

文章标签： java

于 2024-03-09 18:23:10 首次发布

本文链接： https://blog.csdn.net/weixin_53387320/article/details/136588451

版权

本文介绍了使用Java编写的程序，该程序接收查询次数和数字n，计算n的质因数并根据给定的k去除掉出现次数大于等于k的质因子，输出处理后的结果。

摘要由CSDN通过智能技术生成

在这里插入图片描述

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<>();  // 用于存储小于max的所有质数

        // 预处理：找出小于max的所有质数
        for (int i = 2; i < max; i++) {
            check(i, list);
        }

        // 处理每个查询
        for (int i = 0; i < q; i++) {
            long n = in.nextLong();  // 输入的数字n
            long k = in.nextLong();  // 输入的k
            long ans = n;  // 结果初始值为n
            int[] cnt = new int[max];  // 用于存储每个质因子的出现次数

            // 计算n的质因子及其出现次数
            for (int j : list) {
                if (n == 1) break;  // n已经除到1，不需要继续了
                while (n % j == 0) {
                    n /= j;  // 不断除以质因子j
                    cnt[j]++;  // 对应的出现次数加1
                }
            }

            ans /= n;  // 将n除以所有的质因子

            // 根据质因子出现次数是否小于k来更新结果
            for (int j = 0; j < max; j++) {
                if (cnt[j] < k && cnt[j] != 0) {
                    ans /= Math.pow(j, cnt[j]);  // 除去出现次数大于等于k的质因子
                }
            }

            out.println(ans);  // 输出结果
        }
        out.flush();  // 清空缓冲区
    }

    // 检查一个数是否是质数，是则加入list中
    static void check(int n, List<Integer> list) {
        for (int i : list) {
            if (i * i > n) break;  // 如果当前质数的平方已经超过n，说明n是质数
            if (n % i == 0) return;  // n能被当前质数整除，说明不是质数
        }
        list.add(n);  // 没有能整除n的质数，说明n是质数，加入list中
    }

    // 快速输入类，用于读取输入数据
    static class QuickInput {
        StreamTokenizer input = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        
        // 读取一个long类型的数据
        long nextLong() throws IOException {
            input.nextToken();
            return (long) input.nval;
        }
    }
}