网络喷子键盘侠的输入框上已经键入了一句喷人的话，现在他的键盘上只有两个键可用
C：拷贝，可以把输入框的所有内容拷贝下来
P：粘贴，可以在输入框结尾处添加刚刚拷贝的所有内容
请问他至少需要按多少次，可以把输入框里的话复制N次发送出去呢？

样例

如果不可能，则返回{-1, “”}。
我们保证 N >= 0

1
2
3
4
5
6
7
8
9
10
11
12
N = 0
做不到，返回 -1, ""

N = 1
0次：

N = 2
2次：CP

N = 12
7次：CPCPCPP

分析

有的同学可能会误以为这是一个动态规划的题目，
可能是因为有一道题叫做“矩阵乘法”，这个题目相比来说很类似。

实际上因为它可以完全用贪心法，所以没有必要动态规划。

直接采用因式分解，然后把因子加起来就可以了。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// KeyPress accepts target number of repeat times on the screen,
// 	returns times of key pressing & key pressing sequence
func KeyPress(N int) (int, string) {
	var seq string
	if N <= 0 {
		return -1, seq
	}
	var result = 0
	for i := 2; i <= N; {
		if N%i == 0 {
			N = N / i
			result += i
			seq = seq + "C"
			for j := 1; j < i; j++ {
				seq = seq + "P"
			}
		} else {
			i++
		}
	}
	return result, seq
}