CCF-CSP202312-2因子化简

发布时间:2023年12月31日

#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;
} 
 
文章来源:https://blog.csdn.net/m0_72671017/article/details/135304421
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。