# Codechef COPRIME3 ( Mobius Inversion )

https://www.codechef.com/problems/COPRIME3

A Dance with Mobius Function - Posts - Quora

N ≤ 1e5
1 ≤ A[ i ] ≤ 1e6

Mobius 反演的精神在於：將「有多少組合恰好有 gcd = x」這樣限定的式子轉換成「有多少組合的 gcd 為 x 的倍數」，後者不但比較可求，而且很容易可以達到統一計算的加速。

O( MAXA lg MAXA )

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

typedef long long ll;

const int MAXN = ( int ) 1e5;
const int MAXA = ( int ) 1e6;

int N;
int A[ MAXN ];

int mu[ MAXA + 1 ];
int bai_cnt[ MAXA + 1 ]; // baisuu cnt
ll C[ MAXN + 1 ][ 3 + 1 ];

signed main(){
ios::sync_with_stdio( 0 );
cin >> N;
for( int i = 0; i < N; ++i ){
cin >> A[ i ];
++bai_cnt[ A[ i ] ];
}
{ // sieve
mu[ 1 ] = 1;
for( int i = 1; i <= MAXA; ++i ){
for( int j = i + i; j <= MAXA; j += i ){
bai_cnt[ i ] += bai_cnt[ j ];
mu[ j ] -= mu[ i ];
}
}
}
{ // preprocess C( x, 3 )
C[ 0 ][ 0 ] = 1LL;
for( int i = 0; i < MAXN; ++i ){
for( int j = 0; j <= 3; ++j ){
C[ i + 1 ][ j ] += C[ i ][ j ];
if( j + 1 <= 3 ){
C[ i + 1 ][ j + 1 ] += C[ i ][ j ];
}
}
}
}
ll ans = 0LL;
for( int i = 1; i <= MAXA; ++i ){
ans += C[ bai_cnt[ i ] ][ 3 ] * mu[ i ];
}
cout << ans << endl;
return 0;
}
```