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 真的會不知道該不該認真呢._.
解法:
首先我們想求的是這個:
對下列式子作 Mobius 反演,找到對應的 f 函數:
略過證明,可以知道 f 為尤拉的 phi 函數:
( 這個形式很常出現,可以記下來。另外當需要的是若 g = 1 則 1,否則 0,f = mu ( mobius ) 函數。但即使不記這些,一樣可以用 Mobius Inversion 的通式,搭配 Sieve 生出 f 函數。 )
因此問題轉化為求下列式子:
而下列式子也很容易可以求出:
時間 / 空間複雜度:
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; }