因子化简

题目背景

质数（又称“素数”）是指在大于 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$，仅有一个最大素因子 $m$ 可能大于 $\sqrt{n}$，也就是说我们只需要除去 $2\sim \sqrt{n}$ 的素因子就可以得到 $m$，所以对于全部数据 $n\le 10^{10}$，我们只需要求出 $2\sim 10^5$ 中所有质数即可，直接用试除法，稍微优化一下时间复杂度也就 $10^7$，可以通过，如果数据 $n\le 10^{14}$ 就需要使用线性筛法了。

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;
        }
    }
}

C++

#include<bits/stdc++.h>
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;
}

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)

线性筛法

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