Acwing周赛57-数字操作-(思维+分解质因数)

数字操作

题意：
就是给你一个数n，你可以让n乘以任意正整数x，或者让n开根号。问你最小可以达到的数字是多少，达到这个数字最少要多少次操作。

思考：
刚开始以为就是直接暴力跑一遍，一个数让n乘以x，再开方即可。当然这是错的，乘的可能不够。实际上就是对n先分解质因数，首先要保证达到的数最小，那么就看每个质因子的次幂，让所有的次幂都成为最大次幂，然后再一步一步开方，如果当前的次幂不是2的倍数，也就是不能直接开方了，那么就乘以这个数，让他成为2的倍数，所以用个st标记，是否要乘以数，不管乘多少次，我们都可以转化成第一次全部乘完。

代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 1e5+10,M = 2010;

int T,n,m,k;
int va[N];

map<int,int > mp;

signed main()
{
    
	IOS;
	cin>>n;
	if(n==1)
	{
    
		cout<<1<<" "<<0;
		return 0;
	}
	for(int i=2;i<=n/i;i++)
	{
    
		while(n%i==0)
		{
    
			mp[i]++;
			n /= i;
		}
	}
	if(n>1) mp[n]++;
	int maxn = 0,minn = inf,now = 1;
	for(auto t:mp)
	{
    
		now = now*t.fi;
		maxn = max(maxn,t.se);
		minn = min(minn,t.se);
	}
	int sum = 0,st = 0;
	if(minn<maxn) st = 1; //如果有的质因子的次幂不够，那么就要乘数了
	while(maxn>1)
	{
    
		if(maxn&1) //如果此时次幂不是2的倍数，那么乘以now，使得变成2的倍数
		{
    
			st = 1;
			maxn++;
		}
		maxn /= 2;
		sum++;
	}
	cout<<now<<" "<<sum+st; //答案就是质因子的乘积，次数就是开方次数和是否要乘数
	return 0;
}

总结：
多多思考，想一些算法之类的，用不确定的方法肯定不一定对。