BZPRO

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

内存限制：128 MiB 时间限制：10 Sec
提交 提交记录 讨论

题目描述

    农夫约翰正在扩增牛群．通过调整饲料的量，他可以控制牛群中每头母牛所生的小牛的数
量．如果他给每头奶牛喂了相同量的饲料，她们就产下了相同数量的牛犊．开始，他喂了一头母牛，希望通过若干代的饲育得到N只奶牛．假如N= 12，那么约翰应该喂那只最初的奶牛足够的饲料，使其生3只牛犊．第二代牛长大后，他就给她们喂足够的饲料，使它们生下4只牛犊，从而最后一代中有12只牛了．牛一旦生产，约翰就把她卖了．所以，农场里只保留最新一代的牛． 每头牛生牛犊的数量不少于2，且无上限．约翰可以通过多少种不同的方式使最络牛的总数为N(1≤N≤2×109)方法的总数量不超过2×10^9.

输入格式

    整数N.

输出格式

 
    获得N头牛的方式总数．

样例

样例输入


			
    12

样例输出


			
 

 

    8

样例说明

    获得12头牛的方法是(2，2，3).即，第一二代都生产2头，第三代生产3头（一共12头）．其余7种方法为(2，3，2)，(3，2，2)，(3，4)，(4，3)，(12)，(2，6)，(6，2).

数据范围与提示

BZPRO Powered by Remmina.
Github Repository