CA Loves GCD(DP)

CA Loves GCD

题意

给你n个数，从里面任取几个（至少1个），计算它们的gcd，问你所有可能的取法的gcd之和。

对结果模1e8+7（注意是8）

n<=1000

思路

dp[i][j]表示取前i个数时gcd为j的种数。

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

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

对1000内的任意两个数的gcd作预处理，i从0开始。

看！代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e8+7;
const int N=10000010;
int dp[1010][1010]={0};
int gcd[1005][1005];
int a[1010];
/*int ggcd(int a, int b) {
    return b == 0 ? a : ggcd(b, a%b);
}*/

void init(int n)
{
    dp[0][0]=1;
    for(int i=0;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            gcd[i][j]=__gcd(i,j);
            gcd[j][i]=gcd[i][j];
        }
    }
}

int main()
{
    init(1000);
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        int MAX=-1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            MAX=max(MAX,a[i]);
        }
        dp[0][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=MAX;j++)
            {
                dp[i][j]=(dp[i][j]+dp[i-1][j])%MOD;
                dp[i][gcd[a[i]][j]]=(dp[i][gcd[a[i]][j]]+dp[i-1][j])%MOD;
            }
        }
        int ans=0;
        for(int i=1;i<=MAX;i++)
            ans=(ans+1ll*dp[n][i]*i)%MOD;
        printf("%d\n",ans);
    }
    return 0;
}