hdu 5656 CA Loves GCD（dp）

题目的意思就是：
n个数，求n个数所有子集的最大公约数之和。

第一种方法：
枚举子集，求每一种子集的gcd之和，n=1000，复杂度O(2^n)。
谁去用？

所以只能优化！
题目中有很重要的一句话！

We guarantee that all numbers in the test are in the range [1,1000].

这句话对解题有什么帮助？
子集的种数有2^n种，但是，无论有多少种子集，它们的最大公约数一定在1-1000之间。
所以，我们只需要统计1-1000的最大公约数中可以有多少中方法凑成就可以了！

我们就会考虑dp。
官方题解：

我们令dp[i][j]表示在前i个数中，选出若干个数使得它们的gcd为j的方案数，于是只需要枚举第i+1个数是否被选中来转移就可以了。
令第i+1个数为v，当考虑dp[i][j]的时候，我们令$dp[i+1][j] += dp[i][j],dp[i+1][gcd(j,v)] += dp[i][j]。
复杂度O(N*MaxV) MaxV 为出现过的数的最大值。

AC 代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <set>
 6 #include <map>
 7 using namespace std;
 8 #define N 1006
 9 #define MOD 100000007
10 #define ll long long
11 ll n;
12 ll a[N];
13 ll dp[N][N],g[N][N];
14 ll gcd(ll x,ll y){
15    return y==0?x:gcd(y,x%y);
16 }
17 void init(){
18    for(ll i=1;i<=1000;i++){
19       for(ll j=i;j<=1000;j++){
20          g[i][j]=g[j][i]=gcd(i,j);
21       }
22    }
23 }
24 int main()
25 {
26     init();
27     ll t;
28     scanf("%I64d",&t);
29     while(t--){
30        scanf("%I64d",&n);
31        for(ll i=0;i<n;i++){
32           scanf("%I64d",&a[i]);
33        }
34        memset(dp,0,sizeof(dp));
35 
36        for(ll i=0;i<n;i++){
37           dp[i][a[i]]++;
38           for(ll j=1;j<=1000;j++){
39              dp[i+1][j]+=dp[i][j];
40              dp[i+1][j]%=MOD;
41 
42              ll r=g[a[i+1]][j];
43              dp[i+1][r]+=dp[i][j];
44              dp[i+1][r]%=MOD;
45           }
46        }
47        ll ans=0;
48        for(ll i=1;i<=1000;i++){
49           if(dp[n][i]!=0){
50              ans+=i*dp[n][i];
51              ans%=MOD;
52           }
53        }
54        printf("%I64d
",ans);
55     }
56     return 0;
57 }