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

时间：2025-01-07 09:38:08

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 10001≤T≤50, 1≤N≤1000, 1≤A​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[][];

const int MOD=1e8+;

int gcd(int x,int y){return y==?x:gcd(y,x%y);}

int a[];

int gc[][];

int main()

{

    for(int i=;i<=;i++)

    {

        for(int j=i;j<=;j++)

        {

            gc[j][i]=gc[i][j]=gcd(i,j);

        }

    }

    int T;

    scanf("%d",&T);

    while(T--)

    {

        memset(dp,,sizeof(dp));

        dp[][]=;

        int n,v;

        scanf("%d",&n);

        for(int i=;i<=n;i++) scanf("%d",&a[i]);

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=;j++)

            {

              dp[i][j]=(dp[i][j]+dp[i-][j])%MOD;

              dp[i][gc[j][a[i]]]=(dp[i][gc[j][a[i]]]+dp[i-][j])%MOD;

            }

        }

        long long ans=;

        for(long long j=;j<=;j++) ans=(ans+dp[n][j]*j)%MOD;

        printf("%lld\n",ans);

    }

    return ;

}

相关文章