Codeforces 735D《Taxes》

这™什么破题

题面

大概就是规定一个数的花费为它的最大真因子(除了本身以外的最大因数,如果这个数是质数,花费为1)

现在给你一个数 $n$,要求把它拆成几个数相加的形式(也可以不拆),使得拆完后每一个数的花费的和最小

输出这个最小的和

输入输出样例

输入样例#1

1
4

输出样例#1

1
2

输入样例#2

1
27

输出样例#2

1
3

解析

别告诉我你脑子里装的都是暴力

我现在来说几个有趣的性质

说完这道题就做完了

  1. 哥德巴赫猜想(即任意大于2的偶数都可以被拆成两个质数的和)
  2. 对于任意大于5的非质奇数(即不是质数的奇数),都可以被拆成3和两个质数的和(哥德巴赫猜想的一个推论)

好 现在假设哥德巴赫猜想成立 请读者自行证明第二条


依据这两个性质,我们可以对这道题进行如下的分类讨论

  • 当给定的为质数时,花费为1
  • 当给定的为偶数时,根据哥德巴赫猜想可以拆成两个质数,花费为2
  • 给定的数-2为质数时,这个数可以拆成2和给定的数-2两个质数,花费为2
  • 否则这个数可以拆成3和给定的数-3,因为给定的数是奇数,显然给定的数-3是偶数,可以拆成两个质数,花费为3

代码实现

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
#include <iostream>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

int n;

bool isPrime(int x) {
if (x <= 1) return false;
if (x == 2 || x == 3) return true;
for (int i = 2; i * i <= x; ++i) if (x % i == 0) return false;
return true;
}

int main() {
// 这什么破题啊
IMPROVE_IO();
cin >> n;
if (isPrime(n)) cout << 1 << endl;
else if ((n & 1) == 0) cout << 2 << endl;
// 根据哥德巴赫猜想,一个偶数可以被拆成两个质数
else if (isPrime(n - 2)) cout << 2 << endl;
// 这个数字可以被拆成 2 和另一个质数的和
else cout << 3 << endl;
// 这个数字可以被拆成 3 和另一个偶数的和,这个偶数又可以被拆成两个质数
return 0;
}