携程预赛第一场第一题

A<= 10 , B <= 20  

解法：

参加维基百科http://en.wikipedia.org/wiki/B%C3%A9zout‘s_identity

根据Bézout‘s identity我们可以知道，这A+1个自然数能组成和为1(和为-1是一样的)的情况只能是这A+1个自然数互质，简单dp即可。

#include <cstdio>
#include <algorithm>
#include <cstring>

typedef long long ll;

int gcd(int a, int b){
	return b == 0 ? a : gcd(b, a % b);
}

int main(){
	int T;
	ll dp[15][25];
	int mod = 1e9 + 7;
	scanf("%d", &T);
	for(int t = 0; t < T; t++){
		int a, b;
		scanf("%d %d", &a, &b);
		memset(dp, 0, sizeof(dp));
		dp[0][b] = 1;
		for(int i = 1; i <= a; i++){
			for(int j = 1; j <= b; j++){
				for(int k = 1; k <= b; k++){
					dp[i][gcd(j, k)] = (dp[i][gcd(j, k)] + dp[i - 1][j]);
				}
			}
		}
		printf("%I64d\n", dp[a][1]);
	}
}

携程预赛第一场第一题,布布扣,bubuko.com

携程预赛第一场第一题

原文：http://blog.csdn.net/waitfor_/article/details/23699451