Codeforces 735D《Taxes》

三月 23, 2019 1388

这™什么破题

题面

大概就是规定一个数的花费为它的最大真因子（除了本身以外的最大因数，如果这个数是质数，花费为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
33
34
#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;
}