0w1

HR Hyperrectangle GCD ( Mobius Inversion )

https://www.hackerrank.com/challenges/hyperrectangle-gcd

題意:
有 K 個箱子,裡面分別有 [ 1, N[ i ] ] 的數字。現在要從每個箱子里抽一個數字,求其最大公因數。問所有取法可以產生的最大公因數總和。

資料規模:
Constraints
1 <= T <= 1000
2 <= K <= 500
1 <= nk <= 100000
p.s. T * nk * K 明明就很慘... 看到 T 真的會不知道該不該認真呢._.

解法:
首先我們想求的是這個:
f:id:h0rnet:20170311193409p:plain
對下列式子作 Mobius 反演,找到對應的 f 函數:
f:id:h0rnet:20170311193449p:plain
略過證明,可以知道 f 為尤拉的 phi 函數:
f:id:h0rnet:20170311193556p:plain
( 這個形式很常出現,可以記下來。另外當需要的是若 g = 1 則 1,否則 0,f = mu ( mobius ) 函數。但即使不記這些,一樣可以用 Mobius Inversion 的通式,搭配 Sieve 生出 f 函數。 )
f:id:h0rnet:20170311213428p:plain
f:id:h0rnet:20170311213620p:plain
因此問題轉化為求下列式子:
f:id:h0rnet:20170311193609p:plain
而下列式子也很容易可以求出:
f:id:h0rnet:20170311193639p:plain

時間 / 空間複雜度:
O( T * min_n * K )

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

const int MOD = ( int ) 1e9 + 7;
const int MAXN = ( int ) 1e5;

int np[ MAXN + 1 ];
int phi[ MAXN + 1 ];

signed main(){
  { // preprocess phi
    for( int i = 1; i <= MAXN; ++i ){
      phi[ i ] = i;
    }
    for( int i = 2; i < MAXN; ++i ){
      if( np[ i ] ) continue;
      for( int j = i; j <= MAXN; j += i ){
        phi[ j ] = phi[ j ] / i * ( i - 1 );
        np[ j ] = 1;
      }
    }
  }
  ios::sync_with_stdio( 0 );
  int T; cin >> T;
  for( int ti = 0; ti < T; ++ti ){
    int K; cin >> K;
    vector< int > N( K );
    for( int i = 0; i < K; ++i ){
      cin >> N[ i ];
    }
    int minn = *min_element( N.begin(), N.end() );
    int ans = 0;
    for( int i = 1; i <= minn; ++i ){
      int pi = 1;
      for( int j = 0; j < K; ++j ){
        pi = 1LL * pi * ( N[ j ] / i ) % MOD;
      }
      ( ans += 1LL * phi[ i ] * pi % MOD ) %= MOD;
    }
    cout << ans << "\n";
  }
  return 0;
}