互いに素な3つ組の総数

問題

http://www.codechef.com/LTIME13/problems/COPRIME3
整数 N (0 < N < 10⁵) と, N 個の整数 a_0, a_1, ..., a_[n-1] (0 < a_i < 10⁶) が与えられる.
0 < i < j < k <= N として, a_i, a_j, a_k が互いに素となるような (i, j, k) の個数を出力せよ.
(制限時間1秒)

解答

gcd(a_i, a_j, a_k) = m なる (i, j, k) の個数に対する動的計画法で解く.
dp[m] は gcd() = m なる (i, j, k) の個数を表すとして, dp[10⁶] から順に計算していく.
dp[1] が答えとなる.
計算量オーダーは, a_i の最大値を M (=10⁶) として, O(Mlog(M)).

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
const int MAX = 1000000;

int main(int argc, char const* argv[])
{
    int N; cin >> N;
    int cnt[MAX+10] = {};
    for (int i = 0; i < N; i++) {
        int a; cin >> a;
        cnt[a]++;
    }

    vector<ll> dp(MAX+10);
    for (int i = MAX; i; i--) {
        // 入力値のうち i で割り切れるものの個数
        int mults = 0;
        for (int j = i; j <= MAX; j += i) mults += cnt[j];

        // multsから3つ選ぶ組み合わせ (mults C 3)
        dp[i] = (ll)mults*(mults-1)*(mults-2)/6;

        // dp[i*2], dp[i*3], ... を除く
        for (int j = i*2; j <= MAX; j += i) dp[i] -= dp[j];
    }

    cout << dp[1] << endl;
    return 0;
}

この方法だと簡単にnつ組に拡張できる.