E. Singhal and numbers (prime factor decomposition)

https://codeforces.com/gym/102767/problem/E

The question
Give a number n, You can choose less than n As a factor of N.

• If N Prime number , So the answer is $A+\frac{X}{N}$;
• If N Is the sum , So the answer is $B+\frac{X}{N}$;
• If N by 1, So the answer is $C+\frac{X}{N}$.

ask , What is the minimum answer ？

Ideas
To minimize the answer , Be sure to find the largest prime factor , The largest combining factor .
Prime factor decomposition finds the maximum prime factor ,O($\sqrt{n}$).

In order to find the maximum composite number , Sure First find the maximum factor ：n / Minimum prime factor .

• If the maximum factor is prime , It means that there is no maximum combining factor .
• Otherwise, the maximum factor is the maximum resultant factor .

Note that the factor in this question should be less than n, So we can make a special judgment first n In the case of prime numbers .

Code

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a, b, c;

bool isPrim(int x){
    
	if(x == 0 || x == 1) return 0;
	for(int i=2;i<=x/i;i++)
	{
    
		if(x % i == 0) return 0;
	}
	return 1;
}

signed main(){
    
	Ios;
	cin >> T;
	while(T--)
	{
    
		cin >> n;
		cin >> a >> b >> c;
		
		if(isPrim(n)){
    
			cout << c + n << endl;
			continue;
		}
		
		int mprim = -1, mcom = -1;
		int minprim = -1;
		
		int t = n;
		for(int i=2;i<=t/i;i++)
		{
    
			if(t % i == 0)
			{
    
				while(t % i == 0) t/=i, mprim = i;
				
				if(minprim == -1) minprim = i;
			}
		}
		if(t != 1) mprim = t;
		
		int min1 = 1e18, min2 = 1e18, min3 = 1e18;
		min1 = a+n/mprim;
		
		mcom = n/minprim;
		if(!isPrim(mcom)) min2 = b+n/mcom;
		min3 = c+n;
		
		int ans = min(min(min1, min2), min3);
		cout << ans << endl;
	}
	
	return 0;
}