HDU 5656 CA Loves GCD 01背包+gcd

题目链接：

hdu:http://acm.hdu.edu.cn/showproblem.php?pid=5656

bc:http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=683&pid=1002

CA Loves GCD

Accepts: 64 Submissions: 535

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

问题描述

CA喜欢是一个热爱党和人民的优秀同♂志，所以他也非常喜欢GCD（请在输入法中输入GCD得到CA喜欢GCD的原因）。

现在他有N个不同的数，每次他会从中选出若干个（至少一个数），求出所有数的GCD然后放回去。

为了使自己不会无聊，CA会把每种不同的选法都选一遍，CA想知道他得到的所有GCD的和是多少。

我们认为两种选法不同，当且仅当有一个数在其中一种选法中被选中了，而在另外一种选法中没有被选中。

输入描述

第一行TT，表示有TT组数据。

接下来TT组数据，每组数据第一行一个整数NN，表示CA的数的个数，接下来一行NN个整数A_iAi表示CA的每个数。

1 le T le 50,~1 le N le 1000,~1 le A_i le 10001≤T≤50, 1≤N≤1000, 1≤Ai≤1000

输出描述

对于每组数据输出一行一个整数表示CA所有的选法的GCD的和对100000007100000007取模的结果。

输入样例

2 4

1 2 3

输出样例

题解：

　　可以建模为01背包的模型。

　　dp[i][j]表示前i个数的任意组合中gcd等于j的组合数。

　　转移方程有：（刷表法）

　　　　第i个数不取：dp[i][j]+=dp[i-1][j]；

　　　　第i个数要取：dp[i][gcd(a[i],j)]+=dp[i-1][j]；

　　可以离线处理出1000以内任意两个数的gcd值，否则会超时，当然也可以通过减枝来降低时间复杂度（如果dp[i-1][j]=0，就没必要算gcd(a[i],j)了）。

　　初始化有dp[0][0]=1（一个数都没有，则有gcd为0）

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

typedef long long LL;
const int maxn = 1000 + 10;
const int mod = 1e8 + 7;//这里不要写成1e9+7!!!!

int n;
int a[maxn], dp[maxn][maxn];
int g[maxn][maxn];

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

void get_g() {
    for (int i = 0; i <= 1000; i++) {
        for (int j = i; j <= 1000; j++) {
            g[i][j] = g[j][i] = gcd(i, j);
        }
    }
}

void init() {
    memset(dp, 0, sizeof(dp));
}

int main() {
    get_g();
    int tc;
    scanf("%d", &tc);
    while (tc--) {
        init();
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
        }
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 1000; j++) {
                dp[i][j] += dp[i - 1][j]; dp[i][j] %= mod;

                int tmp = g[a[i]][j];
                dp[i][tmp] += dp[i - 1][j]; dp[i][tmp] %= mod;
            }
        }
        LL ans = 0;
        for (int i = 1; i <= 1000; i++) {
            ans += (LL)dp[n][i] * i;
            ans %= mod;
        }
        printf("%lld
", ans);
    }
    return 0;
}

View Code