J. 挑选队列

题目链接：http://www.acmicpc.sdnu.edu.cn/problem/show/1637
看了题解，出题人把1-n的数转化为图上的点去考虑的。如果两个数互质就连一条边，这样我实际上就在求两两都连边或者两两都不连边的三元组有多少个？
直接求麻烦，考虑容斥，用所有情况的三元组减去不符合条件的三元组。
不符合条件的三元组有哪些呢？

图1，三个点中只有一对点之间有边
图2，三个点中只有两对点之间有边
考虑一个点的度：

我们发现图一与图二两种情况其实可以放到一起去算：
不符合条件的情况就是d[i]*(n-d[i]-1)/2，d[i]是i相连的点,(n-d[i]-1)是i不连的点，除2是因为重复计算了一次。
下面就是计算d[i]

如果按照因数来求的话，时间复杂度为O(n√n)，求d的时候维护对倍数的贡献时间复杂度降低至O(nlogn)
代码：(oj有点奇怪，有时ac有时tle，但是如果不用defineintlonglong而是typedef longlongll肯定会过)

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

typedef long long ll;
const int maxn = 2e6+7;

int prime[maxn];
bool vis[maxn];
int mu[maxn];
inline void init(){
    int cnt = 0;
    vis[0] = vis[1] = 1;
    mu[1] = 1;
    for(int i=2; i<maxn; i++){
        if(!vis[i]){
            prime[cnt++]=i;
            mu[i]=-1;
        }
        for(int j=0; j<cnt && i*prime[j]<maxn; j++){
            vis[i*prime[j]] = 1;
            if(i%prime[j]){
                mu[i*prime[j]] = -mu[i];
            }
            else{
                mu[i*prime[j]] = 0;
                break;
            }
        }
    }
}

inline ll cn3(int n){
    return 1LL* n * (n-1) * (n-2) / 6;
}

ll d[maxn];
int main(){
    init();
    int n;
    ll ans = 0;
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j+=i){
            d[j] += mu[i]*(n/i);
        }
    }
    d[1]--;
    for(int i=1; i<=n; i++){
        ans += d[i] * (n-d[i]-1);
    }
    printf("%lld\n",cn3(n)-(ans/2));
}