CCF-Csp算法能力认证，    202312-1仓库规划含解析

前言

推荐书目，在这里推荐那一本《算法笔记》（胡明），需要PDF的话，链接如下

「链接：https://pan.xunlei.com/s/VNvz4BUFYqnx8kJ4BI4v1ywPA1?pwd=6vdq# 提取码：6vdq”复制这段内容后打开手机迅雷App，查看更方便」

希望有大神能够提供改良意见，敬礼！

---------------------------------------------------------------------------------------------------------------------------------

题目

【题目描述】

【输入格式】

【输出格式】

【样例 1 输入】

3

2155895064 3

2 2

10000000000 10

【样例 1 输出】

2238728

1

10000000000

【样例 1 解释】

【样例 2 输入】

【样例 2 输出】

【样例 2 解释】

【样例 3 输入】

【样例 3 输出】

【样例 3解释】

【子任务】

思路分析：

本题的思想比较简单,主要思想就是先算出100000内的素数，因为最大的数字要求是10e10，而10e5之后的素数不可能再满足乘得n，已经不可整除。使用埃式筛选法来筛选出所需的素数。而后尝试n是否可以整除，可以就整除，每次整除都记录下来，这样就会得到该素因子的次数，次数小于k就舍弃，其余的值相乘得到结果。

代码如下：

#include<bits/stdc++.h>//万能头文件 
using namespace std;vector<int> primelist;//使用vector，类似变长数组，这里使用int因为够用 ，
// 素因子的量肯定是较少的 ，满足题设的更少 void getPrime(){//埃式筛选法，思想就是给每一个数*n（0.1.2.3...）得到的值全部都不是素数，这样可以筛选出素数。bool isPrimeList[100001];//通过下标来记录数，内容表示是否为素数 //找到100000以内的所有素数， 即最大可能得测试数开方，//这之后可能还会有素数，但是一定不满足可以整除测试数,除完会有余数，不满足题目要求 //所以可以直接忽略。for(int i = 0;i<=100001;i++){//这里也可以不给0.1赋值，因为没有用到 isPrimeList[i] = true;}isPrimeList[0] =false;isPrimeList[1] =false;//没有用到也赋值，用于区分避免出错 for(int i = 2;i*i<=100001;i++){//使用i*i是因为，该算法中i*i之前的数//（假设10*10之前有，20,30,40...但是分别会被，2,3,4...筛选出来，所以小于i*i的部分可以优化掉） if(isPrimeList[i]){//初始化的时候都是真，后来就可以跳过部分已经被false的 for(int j = i*i;j<=100001;j+=i){isPrimeList[j] = false;//给加上i的所有值标记成false，剩余的就是素数 //如i=10.   100,110,120,130都是非素数//（而10前面筛选过的部分会直接跳过，所以这些在筛选2的时候就已经跳过了）//再有，10在2筛选的过程中也被标记了，所以只是模拟一下，实际上i=10会直接跳过 }}}for(int i = 2;i<=100001;i++){if(isPrimeList[i]){//是素数则存到vector primelist.push_back(i);}}
}
int main(){getPrime();int q;  cin >> q;//查询次数 for(int i = 0;i<q;i++){long long int n,k,result;//只说k>1，可能很大 cin >> n >> k;result=1;//如果没有剩余项就是1 for(int j = 0;j<primelist.size();j++){int times = 0;//times用来记录被除的次数，及结果因数的开发值while(n%primelist[j] == 0){n/=primelist[j];//n除掉素因子 times++;//记录除的次数 }if(times>=k){result*=pow(primelist[j],times); //大于就乘到结果里面 } //小于不用处理，每次循环times会重新变成0 }cout << result << endl;}
}