CCF-CSP202312-2因子化简

#include<iostream>
#include<cmath>
using namespace std;
int q,cnt;
bool st[100010];
int prime[100010];
//bool ispower(int n)//这个判断质数的方法不可行
//{
//	for(int i=2;i*i<=n;i++)
//	{
//		if(n%i==0)
//			return false;
//	}
//	return true;
//}


//Acwing欧拉线性筛法， 只筛st[prime[j]*i]
// 其中prime[j]是最小质因子 
void getprime(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(!st[i]) prime[cnt++]=i;
		for(int j=0;i*prime[j]<=n;j++)
		{
			st[i*prime[j]]=true;
			if(i%prime[j]==0) break;
		}
	}
}
int main()
{
	cin>>q;
	getprime(10000);
	for(int i=0;i<q;i++)
	{
		long long n;
		int k;
		long long res=1;
		scanf("%lld%d",&n,&k);
		for(int j=0;j<cnt;j++)//遍历prime 
		{	
			int t=prime[j];
			
			if(n%t==0)
			{
				int cishu=0;
				while(n%t==0)
				{
					cishu++;
					n/=t;
				}
				if(cishu>=k) res*=pow(t,cishu);
			}
		}
		printf("%lld\n",res);
	}
	return 0;
}