首页 > 代码库 > CA Loves GCD (BC#78 1002) (hdu 5656)

CA Loves GCD (BC#78 1002) (hdu 5656)

CA Loves GCD

 
 Accepts: 135
 
 Submissions: 586
 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 10001T50, 1N1000, 1A?i??1000
输出描述
对于每组数据输出一行一个整数表示CA所有的选法的GCD的和对 100000007100000007 取模的结果。
输入样例
2
2
2 4
3
1 2 3
输出样例
8
10

 

 

dp(i)(j):对前i个数gcd为j的方案数

 1.dp(i+1)(j)+=dp(i)(j)
 2.dp(i+1)(gcd(j,v))+=dp(i)(j)
 3. dp(0)(0)=1
 (
    i:1~1000
    j:1~1000
)
技术分享
#include <cstdio>
#include <cstring>
int dp[1010][1010];
const int MOD=1e8+7;
int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int a[1010];
int gc[1010][1010];
int main()
{
    for(int i=0;i<=1000;i++)
    {
        for(int j=i;j<=1000;j++)
        {
            gc[j][i]=gc[i][j]=gcd(i,j);
        }
    }
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(dp,0,sizeof(dp));
        dp[0][0]=1;
        int n,v;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=1000;j++)
            {
              dp[i][j]=(dp[i][j]+dp[i-1][j])%MOD;
              dp[i][gc[j][a[i]]]=(dp[i][gc[j][a[i]]]+dp[i-1][j])%MOD;
            }
        }
        long long ans=0;
        for(long long j=1;j<=1000;j++) ans=(ans+dp[n][j]*j)%MOD;
        printf("%lld\n",ans);
    }
    return 0;
}
View Code

 

CA Loves GCD (BC#78 1002) (hdu 5656)