hdu5656 CA Loves GCD

2993 단어 dp
제목: n개수ai, n과ai의 범위는 1에서 1000 사이입니다. 이 숫자들이 임의로 조합되지 않는 최대 공약수의 합계인 100000007의 결과를 물어보세요.사고방식: dp[i][j]를 설정하면 전 i 개수 중 임의로 조합된 후의 최대 공약수가 j의 개수임을 나타낸다.그것의 전이 방정식은 바로 dp[i+1][j]+=dp[i][j]이다.만약 dp[i][j]가 존재한다면 현재 a[i+1]와 최대 공약수를 한 번 구합니다. dp[i+1] [gcd(j, a[i])] +=dp[i][j]
#include<bits/stdc++.h>
using namespace std;
const int mod=100000007;
int dp[1010][1010],a[1010];
int gcd(int a,int b) {return b==0? a: gcd(b,a%b);}
int main()
{
    int T;scanf("%d",&T);
    while(T--){
        int n,V=0;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            V=max(V,a[i]);
        }

        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            dp[i][a[i]]=1;
            for(int j=V;j>=1;j--){
                dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
                if(dp[i-1][j]){
                    dp[i][gcd(a[i],j)]=(dp[i][gcd(a[i],j)]+dp[i-1][j])%mod;
                }
            }
        }
        long long ans=0;
        for(int i=1;i<=V;i++) ans=(ans+(long long)i*dp[n][i])%mod;
        printf("%lld
"
,ans); } }

좋은 웹페이지 즐겨찾기