VK Cup 2015 - Finals, online mirror F. Clique in the Divisibility Graph

"As you must know," 怖い…
練習です。

問題

Problem - 566F - Codeforces

解法

dp[n] = (nを約数とする数字の個数)とします。数列 a を直接使うのではなく, b[p] = (数列 a の中に p という数がいくつあるか)という配列を用意しておけば, dp[n] の計算は, MAXN/n で処理することが出来ます(MAXN は数列 a に入る最大の数)。

これはだいたい になるので時間内に間に合います。

const int MAXN = 1000001;
int a[MAXN];
int b[MAXN];
int dp[MAXN];
int n;

int dfs(int cur) {
    if (b[cur] == 0) return 0;
    int& ret = dp[cur];
    if (ret > 0) return ret;
    ret = 0;
    for (int i = 2; i*cur < MAXN; i++) {
        ret = max(ret, dfs(i*cur));
    }
    ret += b[cur];
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        b[a[i]]++;
    }
    int ans = 0;
    for (int i = 1; i < MAXN; i++) {
        if (dp[i] == 0) ans = max(ans, dfs(i));
    }
    cout << ans << endl;
    return 0;
}