CCF-CSP 32-2 因子化简（prime）【C++】考点：素数因子分解（试除法）

题目

TUOJhttps://sim.csp.thusaac.com/contest/32/problem/1

思路参考：202312（第32次）CCF CSP真题202312-1,2讲解_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1J5411z7bV?vd_source=5366be93f43e6a40161aecaec29f4a2a&spm_id_from=333.788.videopod.sections

思路

核心思路：用map<int,int>mp存储每个因子的幂次，从因子p=2开始，如果能整除就除p，需要注意的是通过这种试除法得到的自然都是素数因子

代码

可以让AI总结一下代码逻辑

/*
因子分解
*/
#include<bits/stdc++.h>
using namespace std;
#define endl '\\n'
#define ll long long
map<ll,int>mp;

void solve(){
int q; cin>>q;
while(q–){
mp.clear();//WARN:全局数组记得每组数据都清空，不然就弄成局部的
ll n; int k; cin>>n>>k;
int p=2; //因子
while(n!=1){
if(n%p==0){
mp[p]++;
n/=p;
}
else p++;
}
ll ans=1;
for(auto t:mp)
if(t.second>=k) ans*=pow(t.first,t.second); //warn:乘上该因子的幂次
cout<<ans<<endl;
}
}

int main(){
ios::sync_with_stdio(0),cin.tie(0);
solve();
return 0;
}