题目：
聪明的猴子
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1123 Accepted Submission(s): 294
Problem Description
森林中有一排香蕉树（无限长），一只猴子站在其中一棵树上，猴子在跳跃前要先抽取一张卡片，卡片上写有A+1个自然数，其中最后一个是B，前A个数只能小于等于B，卡片上的数字可以相同。猴子每次跳跃先从卡片上任选一个自然数C，然后向左、或向右跳C棵树。猴子的任务是：跳到与它左边相邻的香蕉树上时，就可以吃掉上面的香蕉。
例如，当A=2，B=4时，对于卡片(2, 3, 4)，猴子就可以吃到香蕉：它可以先向左跳3棵树，再向右跳两棵树。而对于卡片(2, 2, 4)，猴子则怎么也不可能跳到它左边相邻的香蕉树上。
当确定A和B后，则一共可以有B^A张不同的卡片。问题是，在这所有的卡片中，有多少张可以让猴子完成任务。
Input
第1行k,表示有k组测试数据，k<=100
第2至k+1行，每行两个自然数A和B，以一个空格分开 （A<= 10 , B <= 20)。
Output
共k行，每行的数字代表每组数据中，可以让猴子跳到它左边相邻香蕉树的卡片数。
Sample Input
3
2 3
4 8
5 13
Sample Output
8
3840
371292
思路：（该题数据比较小） 对于B^A张卡片，只有卡片上的所有数字两两间的GCD == 1 的情况下，才可以让猴子吃到香蕉。由于求GCD运算满足交换律，所以这样考虑：卡片上一定有数字 B ，所以将只有一个数 B 的卡片看成初始状态，用dp（i，j）记录当在只有 B 一个数字的卡片上 加入 i 个数字（可以重复）的时候 GCD = j 时的可取卡片的数量。s 枚举所有数字，转移方程： dp( i，gcd( s, j ) ) += dp(i-1，j)。这样就可以重复利用前面的运算结果。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 30 int dp[maxn][maxn];
int gcd(int a, int b)
{
while(a)
{
int t = a;
a = b % a;
b = t;
}
return b;
} void test(int a, int b)
{
for(int i = 0; i <= a; i++)
{
for(int j = 0; j <= b; j++)
cout<<dp[i][j]<<" ";
cout<<endl;
}
}
int main()
{
int a, b;
while(scanf("%d%d",&a,&b) != EOF)
{
memset(dp, 0, sizeof(dp));
dp[0][b] = 1;
for(int i = 1; i <= a; i++)
for(int j = 1; j <= b; j++)
if(dp[i-1][j])
for(int s = 1; s <= b; s++)
dp[i][gcd(s,j)] += dp[i-1][j];
//test(a,b);
cout<<dp[a][1]<<endl;
}
}
这道题是poj 1091的改编，改小了数据。