Acdream 1114 Number theory 莫比乌斯反演

#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
const int INF = 0x7fffffff;
const int MAXN = 222222 + 5;

LL ans;
int n, mx, a[MAXN];
int pCnt, vis[MAXN], prime[MAXN];
int mu[MAXN], cnt[MAXN], num[MAXN];
#define max(a, b) (a) > (b) ? (a) : (b)

void mobius(int n)
{
    pCnt = -1, vis[1] = mu[1] = 1;

    for(int i = 2; i <= n; ++ i)
    {
        if(!vis[i])
        {
            prime[++ pCnt] = i;
            mu[i] = -1;
        }

        for(int j = 0; j <= pCnt && i * prime[j] <= n; ++ j)
        {
            vis[i * prime[j]] = 1;

            if(i % prime[j])
                mu[i * prime[j]] = ~mu[i] + 1;
            else
                mu[i * prime[j]] = 0;
        }
    }
}

int main()
{
    mobius(222222);
    cin.sync_with_stdio(false);

    while(cin >> n)
    {
        ans = 0, mx = -INF;
        memset(cnt, 0, sizeof(cnt));
        memset(num, 0, sizeof(num));

        for(int i = 1; i <= n; ++ i)
        {
            cin >> a[i];
            mx = max(mx, a[i]);
        }

        for(int i = 1; i <= n; ++ i)
            ++ num[a[i]];

        for(int i = 1; i <= mx; ++ i)
            for(int j = i; j <= mx; j += i)
                cnt[i] += num[j];

        for(int i = 1; i <= mx; ++ i)
            ans += (mu[i] * (LL)cnt[i] * (cnt[i] - 1)) >> 1;

        cout << ans << endl;
    }

    return 0;
}