杭电5656 CA Loves GCD

野性酷女 2022-07-25 18:58 109阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=5656][http_acm.hdu.edu.cn_showproblem.php_pid_5656]

题目大意：给你n个不重复的数字A(1<=n<=1000,1<=A<=1000 )，你每次可以从中选取若干个数字(至少一个)，并对它们求GCD,这样会有很多种选法，你需要找出每一种选法的GCD，然后将它们求和并对100000007取余。

解题思路：这道题用dp,dp\[i\]\[j\],i表示前i个数，j表示gcd为j的个数

初始化：

for(int i=0; i<n; i++)  dp[i][a[i]]=1;

递推：

if(dp[i-1][j])
     { 
     int t=gcd(a[i],j);
     dp[i][t]=(dp[i-1][j]+dp[i][t])%mod;
     }
    dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;

然后递推我是找规律出来的，举个例子，假如n=5  
2 3 4 6  
dp\[2\]\[1\]=1  
dp\[2\]\[2\]=1  
dp\[2\]\[3\]=1

如果在后面加上4,相当于多了 2 4,3 4,2 3 4 这几组数

dp\[3\]\[1\]=1+2=3  
2=dp\[2\]\[3\]+dp\[2\]\[1\]  
gcd(4,3)=1  
gcd(4,1)=1

dp\[3\]\[2\]=1+1 =2  
1=dp\[2\]\[2\]  
gcd(4,2)=2

dp\[3\]\[3\]=1  
dp\[3\]\[4\]=1

到这里规律还不是很明显再写一层

在后面加上6，相当于多了 2 6，3 6，4 6，2 3 6，2 4 6，3 4 6 ，2 3 4 6这几对数

dp\[4\]\[***1***\]=dp\[3\]\[1\]+**3**  
**3**=dp\[3\]\[1\];  
***1***=gcd(6,1)

dp\[4\]\[*2*\]=dp\[3\]\[2\]+**3**  
**3**=dp\[3\]\[2\]+dp\[3\]\[4\]  
*2*=gcd(6,2)=gcd(6,4)

dp\[4\]\[*3*\]=dp\[3\]\[3\]+**1**  
**1**=dp\[3\]\[3\]  
*3*=gcd(6,3)

dp\[4\]\[6\]=1

从这里我们看出来了，如果上一项dp\[i-1\]\[j\]不为0，就在当前循环j=gcd(a\[i\],j)的位置上加上dp\[i-1\]\[j\]。

具体代码

#include <vector>
    #include <list>
    #include <map>
    #include <set>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <bitset>
    #include <algorithm>
    #include <functional>
    #include <numeric>
    #include <utility>
    #include <sstream>
    #include <iostream>
    #include <iomanip>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    #include <ctime>
    #include <cassert>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    typedef long long LL;
    int dp[1005][1005];
    int a[1005];
    int gcd(int x, int y)
    {
        int z;
        while(y) z = y, y = x%y, x = z;
        return x;
    }
    
    int main()
    {
        int t;
        RI(t);
        while(t--)
        {
            int n;
            RI(n);
            mem(dp);
            mem(a);
            for(int i=0; i<n; i++)  RI(a[i]);
            sort(a,a+n);
            for(int i=0; i<n; i++)  dp[i][a[i]]=1;
            for(int i=1; i<n; i++)
            {
                for(int j=a[i]; j>0; j--)
                {
                    if(dp[i-1][j])
                    {
                        int t=gcd(a[i],j);
                        dp[i][t]=(dp[i-1][j]+dp[i][t])%100000007;
                    }
                    dp[i][j]=(dp[i][j]+dp[i-1][j])%100000007;
                }
            }
            long long int ans=0;
            for(int i=1; i<=a[n-1]; i++)
                ans=(ans+(LL)dp[n-1][i]*(LL)(i))%100000007;
            cout<<ans<<endl;
        }
        return  0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5656]: http://acm.hdu.edu.cn/showproblem.php?pid=5656