AcWing 5416. 因子化简 (试除法分解质因数 —— 模板)
原题链接
简单
作者:
杨睿卿
,
2024-04-12 21:22:42
,
所有人可见
,
阅读 14
试除法分解质因数 —— 模板题
模板
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
int s = 0;
while (x % i == 0) x /= i, s ++ ;
cout << i << ' ' << s << endl;
}
if (x > 1) cout << x << ' ' << 1 << endl;
cout << endl;
}
题解
#include<iostream>
#include<cmath>
using namespace std;
typedef long long LL;
LL q,n,k;
int main()
{
cin>>q;
while(q--)
{
cin>>n>>k;
pair<LL,LL> p[100005];
//int prime[100005];
int cnt=0;
for(int i=2;i<=n/i;i++)
{
int s=0;
while(n%i==0) s++,n/=i;
p[cnt++]={i,s};
}
if(n>1) p[cnt++]={n,1};
LL ans=1;
for(int i=0;i<cnt;i++)
{
if(p[i].second>=k) ans*=pow(p[i].first,p[i].second);
}
cout<<ans<<endl;
}
return 0;
}