# HR Hyperrectangle GCD ( Mobius Inversion )

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

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

( 這個形式很常出現，可以記下來。另外當需要的是若 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;
}
```