codeforces #382 div2 D. Taxes(哥德巴赫猜想)

题目链接

题意:一个人有n元前,他要交的税是n的最大因子(除n外),现在这个投机倒把者想把前分成k部分(k为大于等于1的任意值)每部分不能为1,分别交税,问最少交多少税。

思路:要说因子小。。很容易想到素数。。。然后就很容易想到了维基百科_哥德巴赫猜想

内容是:任何一个大于2的偶数可以写成两个素数的和。

(虽然是一个猜想没有被证明。。。但是1E9这种级别正确性还是很显然的2333

那么任何大于2的偶数,答案就是2

奇数可以分成一个3和一个偶数,答案为3.

不过这可能还不够优,这也是这道题的两个trick所在:

如果该数本身为素数,那么不用分(k取1),答案为1

如果该数减去2为素数,那么答案为2.

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz