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

1 \le T \le 50,~1 \le N \le 1000,~1 \le A_i \le 10001≤T≤50, 1≤N≤1000, 1≤Ai≤1000

输出描述

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

输入样例

输出样例

8

10

/*

hdu 5656 CA Loves GCD(n个任选k个的最大公约数和)

给你n个数,每次任选k个数出来求GCD,求所有不重复情况的和

开始试了好几次都TLE,卒。

1.给出的题解是可以用dp来解决,dp[i][j]表示前i个数的GCD为j的个数情况

2.求出给出数中所有i的倍数的个数lan[i],那么它的抽取方案数2^lan[i]-1,再利用容斥原理

可以处理出最大公约数为i的方案数

hhh-2016-04-03 14:29:30

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <functional>

using namespace std;

#define lson  (i<<1)

#define rson  ((i<<1)|1)

typedef long long ll;

const int mod = 1e8+7;

const int maxn = 1005;

int mm = 1000;

int gc[maxn][maxn];

ll dp[maxn][maxn];

int a[maxn];

int gcd(int a,int b)

{

    while(a%b)

    {

        int t = a%b;

        a = b;

        b = t;

    }

    return b;

}

int main()

{

    int n,m;

    int t;

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

    {

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

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

    }

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        memset(dp,0,sizeof(dp));

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

        {

            scanf("%d",&a[i]);

        }

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

        {

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

            {

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

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

            }

            dp[i][a[i]]++;

        }

        ll ans = 0;

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

        {

            ans = (ans+(ll)i*dp[n][i]%mod)%mod;

        }

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

    }

    return 0;

}

/*

hdu 5656 CA Loves GCD(n个任选k个的最大公约数和)

hhh-2016-04-02 22:14:36

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <functional>

#include <vector>

using namespace std;

#define lson  (i<<1)

#define rson  ((i<<1)|1)

typedef long long ll;

const int maxn = 1050;

int mm = 1000;

ll bin[maxn];

const ll mod = 100000007;

vector<int >vec;

ll fa[maxn];

ll lan[maxn];

int main()

{

    int T,x,n;

    bin[0] = 1;

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

    {

        bin[i] = bin[i-1]<<1;

        bin[i] %= mod;

    }

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        memset(lan,0,sizeof(lan));

        memset(fa,0,sizeof(fa));

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

        {

            scanf("%d",&x);

            lan[x]++;

        }

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

        {

            ll t = 0;

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

                t += lan[j];

            fa[i] = bin[t]-1;

        }

        ll ans = 0;

        for(int k = mm; k; k--)

        {

            for(int t = k+k; t <=mm; t+=k)

                fa[k] = (fa[k]-fa[t]+mod)%mod;  //减去抽取到不包含k的情况

            ans=(ans+k*fa[k]%mod)%mod;

        }

        printf("%I64d\n",ans%mod);

    }

    return 0;

}

秒客网

hdu 5656 CA Loves GCD(n个任选k个的最大公约数和)

CA Loves GCD

相关文章