常规质数因子
带相关资料抄写
稍加修改指数的筛选部分

include

include<math.h>

typedef long long ll;
using namespace std;
bool isprime(ll n){
int i;
if(n<=1) return false;
int sq=(int)sqrt(1.0n);
for(i=2;i<=sq;i++){
if(n%i==0) return false;
}
return true;
}
const int maxn=10010;
int prime[maxn],pnum=0;
void findprime(){
int i;
for(i=2;i<=1e5;i++){
if(isprime(i)) prime[pnum++]=i;
}
}
struct factor{
int x,cnt;
}fac[10];
int main() {
int q;
scanf("%d",&q);
findprime();
ll n;
int k;
while(q--){
int num=0;
int i;
ll sum=1;
scanf("%lld",&n);
scanf("%d",&k);
int sq=(int)sqrt(1.0n);
for(i=0;i<pnum&&prime[i]<=sq;i++){
if(n%prime[i]0){
fac[num].x=prime[i];
fac[num].cnt=0;
while(n%prime[i]0){
fac[num].cnt++;
n/=prime[i];
}
num++;
}
if(n==1) break;
}
if(n!=1){
fac[num].x=n;
fac[num++].cnt=1;
}
for(i=0;i<num;i++){
if(fac[i].cnt>=k) sum*=pow(fac[i].x,fac[i].cnt);
}
printf("%lld\n",sum);

}

return 0;

}