BOJ 8291 Coprime Numbers

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

길이가 n인 배열에서 서로소 쌍의 수를 구하는 문제

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;
}