AcWing 5416. 因子化简
原题链接
简单
作者:
Horiki1
,
2024-03-11 08:44:13
,
所有人可见
,
阅读 31
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll = long long;
unordered_map<int, int> primes;
void f(ll n) {
for (ll i = 2; i <= n / i; i++) {
if (n % i) continue;
while (n % i == 0) n /= i, primes[i] ++;
}
if (n > 1) primes[n] ++;
}
int main()
{
int q; cin >> q;
while (q--) {
primes.clear();
ll n, k; cin >> n >> k;
f(n);
ll ans = 1;
for (auto prime : primes) {
if (prime.y >= k)
for (int i = 1; i <= prime.y; i++)
ans *= prime.x;
}
cout << ans << endl;
}
return 0;
}