C++14(g++5.4) 解法, 执行用时: 416ms, 内存消耗: 23824K, 提交时间: 2020-03-24 11:19:39

#include <bits/stdc++.h>
using namespace std;

const int MAXN=3010;
int mod=998244353;
int dp[MAXN][2010];
int arr[MAXN];
int n;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",arr+i);
    for(int i=1;i<=n;i++){
        dp[i][arr[i]]=1;
        for(int j=1;j<=2000;j++){
            int gcd=__gcd(j,arr[i]);
            dp[i][j]+=dp[i-1][j];
            dp[i][gcd]=(dp[i-1][j]+dp[i][gcd])%mod;
        }
    }
    printf("%d",dp[n][1]);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 225ms, 内存消耗: 488K, 提交时间: 2019-09-15 11:28:36

#include <cstdio>
#include <algorithm>

int n, a;
int f[2001];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a);
		for (int j = 1; j <= 2000; j++)
			if (f[j]) (f[std::__gcd(a, j)] += f[j]) %= 998244353;
        f[a]++;
    }
	printf("%d", (long long)f[1] % 998244353);
}