Codeforces 1062B Math题解

题解:

分解质因数
n = p 1 a 1 p 2 a 2 . . . p k a k , 发 现 求 p 1 p 2 . . . p k 即 可 n=p_1^{a_1}p_2^{a_2}...p_k^{a^k},发现求p_1p_2...p_k即可 n=p1a1p2a2...pkak,p1p2...pk
找到a的最大值,求比他小的2^x,求出
p 1 2 x p 2 2 x . . . p k 2 x p_1^{2^x}p_2^{2^x}...p_k^{2^x} p12xp22x...pk2x
然后开方2^x次即可

注意还有一些数字本身就是最小结果,特判一下就好

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
pair<int, int> solve(int n)
{
   
	if (n <= 1) return make_pair(n, 0);
	int res = 1, mx = 0, mn = 20;
	for (int i = 2; i*i <= n; i++)
	{
   
		if (n%i == 0)
		{
   
			res *= i;
			int cnt = 0;
			while (n%i == 0) n /= i, cnt++;
			mx = max(cnt, mx);
			mn = min(cnt, mn);
		}
	}
	if (n > 1) res *= n, mx = max(1, mx), mn = min(1, mn);
	int t = ceil(log2(mx)) + 1e-8;
	if (mn == mx && (1 << t) == mx) return make_pair(res, t);
	else return make_pair(res, t + 1);
}
int main(void){
   
	while (cin >> n)
	{
   
		pair<int, int> ans = solve(n);
		cout << ans.first << ' ' << ans.second << endl;
	}
	return 0;
}