第32次CCF计算机软件能力认证-2-因子化简

因子化简

刷新 

时间限制： 2.0 秒

空间限制： 512 MiB

下载题目目录（样例文件）

题目背景

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

题目描述

小 P 同学在学习了素数的概念后得知，任意的正整数 nn 都可以唯一地表示为若干素因子相乘的形式。如果正整数 nn 有 mm 个不同的素数因子 p1,p2,⋯,pmp1​,p2​,⋯,pm​，则可以表示为：n=p1t1×p2t2×⋯×pmtmn=p1t1​​×p2t2​​×⋯×pmtm​​。

小 P 认为，每个素因子对应的指数 titi​ 反映了该素因子对于 nn 的重要程度。现设定一个阈值 kk，如果某个素因子 pipi​ 对应的指数 titi​ 小于 kk，则认为该素因子不重要，可以将 pitipiti​​ 项从 nn 中除去；反之则将 pitipiti​​ 项保留。最终剩余项的乘积就是 nn 简化后的值，如果没有剩余项则认为简化后的值等于 11。

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

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

输入格式

从标准输入读入数据。

输入共 q+1 行。

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

接下来 qq 行每行包含两个正整数 nn 和 kk，表示一个查询。

输出格式

输出到标准输出。

输出共 q 行。

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

样例输入

3
2155895064 3
2 2
10000000000 10

样例输出

2238728
1
10000000000

样例解释

查询一：

• n=23×32×234×107n=23×32×234×107

• 其中素因子 33 指数为 22，107107 指数为 11。将这两项从 nn 中除去后，剩余项的乘积为 23×234=223872823×234=2238728。

查询二：

• 所有项均被除去，输出 11。

查询三：

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

子任务

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

80%80% 的测试数据满足：n≤1e5；

全部的测试数据满足：1<n≤1e10 且 1<k,q≤10

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long q, n, k;
    cin >> q;

    while (q--)
    {
        cin >> n >> k;
        long long ans = 1;
        map<int, int> mp;

        for (int i = 2; i <= n; i++)
        {
            if (n % i == 0)
            {
                while (n % i == 0)
                {
                    n = n / i;
                    mp[i]++;
                }
            }
            else
                continue;
        }
        for (auto i : mp)
        {
            if (i.second >= k)
            {
                while (i.second--)
                    ans *= i.first;
            }
        }
        cout << ans << endl;
    }
}