Acwing weekly contest 57- digital operation - (thinking + decomposition of prime factor)

Digital operation

The question ：
Just give you a number n, You can let n Multiply by any positive integer x, Or let n Square root . What is the minimum number you can reach , How many operations does it take to reach this number .

reflection ：
At first, I thought it was just a direct violent run , One number n multiply x, Then you can prescribe the formula . Of course it's wrong , It may not be enough . It's actually right n First, we decompose the prime factor , First of all, make sure that the number reached is the minimum , So let's look at the power of each prime factor , Let all powers become the largest power , Then one step at a time , If the current power is not 2 Multiple , That is, you can't directly prescribe the square , Then multiply by this number , Make him 2 Multiple , So use a st Mark , Whether to multiply by the number , No matter how many times , We can all multiply it all for the first time .

Code ：

#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; // If the power of some prime factors is not enough , Then it's a multiplier 
	while(maxn>1)
	{
    
		if(maxn&1) // If the power is not 2 Multiple , Then multiply by now, Make into 2 Multiple 
		{
    
			st = 1;
			maxn++;
		}
		maxn /= 2;
		sum++;
	}
	cout<<now<<" "<<sum+st; // The answer is the product of prime factors , The number of times is the number of square root and whether to multiply 
	return 0;
}

summary ：
Think more , Think of some algorithms , It is certainly not right to use uncertain methods .