E. Singhal and Numbers（质因数分解）

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

题意
给定一个数 n，可以选择小于 n 的因数作为 N。

• 如果 N 是质数，那么答案为 $A+\frac{X}{N}$;
• 如果 N 是合数，那么答案为 $B+\frac{X}{N}$;
• 如果 N 为1，那么答案为 $C+\frac{X}{N}$.

问，答案最小是多少？

思路
为了使答案最小，一定要找最大的质因数，最大的合因数。
质因数分解找到最大质数因子，O($\sqrt{n}$).

为了找到最大的合数，可以先找到最大因数：n / 最小质因数。

• 如果最大因数是质数的话，说明其没有最大合因数。
• 否则最大因数就是最大合因数。

注意此题中因数要小于 n，所以可以先特判掉 n 是质数的情况。

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59