Codechef COPRIME3 ( Mobius Inversion )

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

可以先看這個連結了解 Mobius Inversion 是什麼：
A Dance with Mobius Function - Posts - Quora

題意：
給 N 個數字的數列 A，問有多少對 ( i, j, k ) 滿足 i < j < k 且 gcd( A[ i ], A[ j ], A[ k ] ) = 1。

資料規模：
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;
}