hdu 5656 CA Loves GCD(n個任意k個の最大公約数和)

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     。
          ，                    ，              。

説明の入力

    $T$，    $T$    。
    $T$    ，            $N$，  CA     ，      $N$     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    $100000007$      。

入力サンプル

2
2
2 4
3
1 2 3

出力サンプル

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 
#include 
#include 
#include 
#include 
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
",ans);
    }
    return 0;
}

 

 

/*
hdu 5656 CA Loves GCD(n   k        )

hhh-2016-04-02 22:14:36
*/
#include 
#include 
#include 
#include 
#include 
#include 
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;
vectorvec;
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
",ans%mod);
    }
    return 0;
}

　　
 
 
転載先:https://www.cnblogs.com/Przz/p/5409581.html