Mean:
給出一個集合，有兩種計算集合的值的方式:
1 對于集合的一種排列方式，求它任意區間的gcd，将所有區間的gcd值加起來，即為該排列方式的值；将集合所有排列方式的值加起來即為集合的值;
2 對于集合，任意取k個數，對于取出k個數,值為k個數的gcd*k;k從1-n(集合總個數)，加起來即為集合的值如果集合的值相同，則輸出該值，否則輸出較大的值。
analyse:
詳細分析：http://blog.csdn.net/firstlucker/article/details/47128347
對于方式1，我們計算gcd為i有多少種情況
令F[i]表示gcd為i的倍數的情況總數
則F[i]=∑C(cnt[i],k)*k!*(n-k+1)!
k從1到cnt[i] cnt[i]為集合中i的倍數的數的個數
根據莫比烏斯函數(其中d為n的倍數)
這樣就可以先根據公式算出F[i]的值，預處理出莫比烏斯函數的系數，再采用類似素數篩的方式算出f[i],f[i]為gcd為i的情況數，則答案為∑i*f[i] (i從1-集合的最大值).
同理：對于方式2， F[i]=cnt[i]*2^(cnt[i]-1) 同上采用莫比烏斯反演算出f[i],答案即為 ∑i*f[i] (i從1-集合的最大值)
最後比較2個答案，選取較大的值輸出即可。
兩種形式，用于容斥原理的簡化，預處理出系數（nlongn）即可建邊算出答案
Time complexity: O(N*logN)
Source code: