常用莫比乌斯套路










void sieve() {
    F[1]=sum[1]=1;
    for (int i=2;i<=10000000;i++) {
        if (!flag[i]) prime[++cnt]=i,F[i]=1-i;
        for (int j=1;j<=cnt&&i*prime[j]<=10000000;j++) {
            flag[i*prime[j]]=1;
            if (i%prime[j]==0) {//不互质
                F[i*prime[j]]=F[i];
                break;
            }
            F[i*prime[j]]=F[i]*F[prime[j]];//互质
        }
        sum[i]=sum[i-1]+F[i]*i;
    }
}