CCF-Csp算法能力认证， 202312-2因子化简含解析
CCF-Csp算法能力认证， 202312-1仓库规划含解析
前言
推荐书目，在这里推荐那一本《算法笔记》（胡明），需要PDF的话，链接如下
「链接：https://pan.xunlei.com/s/VNvz4BUFYqnx8kJ4BI4v1ywPA1?pwd=6vdq# 提取码：6vdq”复制这段内容后打开手机迅雷App，查看更方便」
希望有大神能够提供改良意见，敬礼！
---------------------------------------------------------------------------------------------------------------------------------
题目
【题目描述】
【输入格式】
【输出格式】
【样例 1 输入】
32155895064 32 210000000000 10【样例 1 输出】
2238728110000000000【样例 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;
}
}
原文地址：https://blog.csdn.net/weixin_64084409/article/details/140591621
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！