#P3366. [Usaco2004 Feb]Breeding 奶牛饲育

    ID: 2555 传统题 1000ms 512MiB 尝试: 43 已通过: 26 难度: 4 上传者: 标签>难度分类普及数论约数成对枚举动态规划计数 DPCF1500Orange

[Usaco2004 Feb]Breeding 奶牛饲育

[USACO 2004 Feb] Breeding 奶牛饲育

题目描述

约翰从一头母牛开始扩增牛群。他可以调节饲料用量,使同一代的每头母牛都产下相同数量的牛犊。每头母牛在一代中至少产下 22 头牛犊,产仔数没有上限。母牛产仔后就会被卖掉,因此农场里只保留最新一代的牛。

例如,开始时让唯一的母牛产下 33 头牛犊,再让这 33 头牛各产下 44 头牛犊,就能得到 1212 头牛。两种方法只要有一代每头牛的产仔数不同,或者经历的代数不同,就视为不同的方法。

求得到恰好 NN 头牛的方法数。若 N=1N=1,可以保留最初的一头牛,不进行繁殖。

输入格式

从标准输入读入一行一个整数 NN。

输出格式

向标准输出输出一行一个整数,表示方式总数。

12
8

样例解释

一种方法是 (2,2,3)(2,2,3),即前两代每头产 22 头,第三代每头产 33 头。其他七种方法是 (2,3,2)(2,3,2)、(3,2,2)(3,2,2)、(3,4)(3,4)、(4,3)(4,3)、(12)(12)、(2,6)(2,6) 和 (6,2)(6,2)。

数据范围与约定

1≤N≤2×1091\le N\le 2\times 10^9,方法总数不超过 2×1092\times 10^9。