TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4672
  • Problem
  • P4672Let it Bead
    Limits : Time Limit : 1000 MS   Memory Limit : 65536 KB
    Description

    有c种颜色的珠子,现在要得到一条长度为s的项链。如果两条项链通过旋转或者翻转之后完全相同,那么视作同一种项链。给定c和s,求出能构成多少种不同的项链。

    Input Format

    多组询问。

    每组询问占一行,每行两个用空格间隔的正整数c,s,分别代表珠子的颜色总数、项链的长度。

    输入数据以c=s=0结束。

    Output Format

    每组询问占一行,输出一个正整数,表示不同种类的项链数。

    Sample Input

    1 1
    2 1
    2 2
    5 1
    2 5
    2 6
    6 2
    0 0

    Sample Output

    1
    2
    3
    5
    8
    13
    21

    Hint

    对于所有数据,保证cs<=32。

    下面是c=2,s=5时的所有情况:


    Source  POJ2409,感谢rgnoH翻译并造数据