문제: https://www.acmicpc.net/problem/8291

길이가 n인 배열에서 (gcd(arr[i], arr[j]) = 1, 1 <= i < j <= n)인 (i, j) 쌍의 개수를 구하는 문제

배열 4개만 정의하면 쉽게 풀린다.

a[i]: arr[]에서 i의 개수
b[i]: arr[]에서 i의 배수의 개수
c[i]: gcd(arr[], arr[])가 i의 배수인 개수
d[i]: gcd(arr[], arr[])가 i인 개수

a[], b[], c[]는 그냥 구하면 되고
d[]는 뒷부분부터 채워서 이미 값이 들어간 d[ki]를 이용해 d[i] = c[i] - sum(d[ki])으로 구하면 된다.

A = max(arr[]) //코드에서 MAXN

a[] //O(n)
b[] //O(A log A)
c[] //O(A)
d[] //O(A log A)

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

const int MAXN = 3e6 + 10;

ll a[MAXN], b[MAXN], c[MAXN], d[MAXN];

int main(void)
{
    ios_base::sync_with_stdio(0);   cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        int now;
        cin >> now;
        ++a[now];
    }
    for(int i = 1; i < MAXN; ++i)
        for(int j = i; j < MAXN; j += i)
            b[i] += a[j];

    for(int i = 1; i < MAXN; ++i)
        c[i] = b[i] * (b[i] - 1) / 2;

    for(int i = MAXN - 1; i >= 1; --i)
    {
        d[i] = c[i];
        for(int j = i + i; j < MAXN; j += i)
            d[i] -= d[j];
    }
    cout << d[1];
    return 0;
}

도대체 이걸 어떻게 풀지;;;;;