[Usaco2004 Feb]Breeding 奶牛饲育

时间限制:10s      空间限制:128MB

题目描述

    农夫约翰正在扩增牛群.通过调整饲料的量,他可以控制牛群中每头母牛所生的小牛的数
量.如果他给每头奶牛喂了相同量的饲料,她们就产下了相同数量的牛犊.开始,他喂了一头母牛,希望通过若干代的饲育得到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).

提示

没有写明提示


题目来源

Orange

Menuappsclose