题目链接：

hdu:

bc:

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_iA​i​​表示CA的每个数。

1 \le T \le 50,~1 \le N \le 1000,~1 \le A_i \le 10001≤T≤50, 1≤N≤1000, 1≤A​i​​≤1000

输出描述

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

输入样例

2

2

2 4

3

1 2 3

输出样例

8

10

题解：

　　可以建模为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
      
       #include
       
        #include
        
         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\n", ans);    }    return 0;}