NOJ 2079 Prime （莫比烏斯反演）

 

Prime

時間限制(普通/Java):1000MS/3000MS 運行內存限制:65536KByte
總提交:267 測試通過:11

比賽描述
給定n個數,求兩兩互斥的對數。互斥是指兩個數的最大公約數是1

輸入
第一行為樣例數T(T<=5)
對每個樣例，第一行為一個整數n(2= 接下來一行包含n個數，a1,a2,…,an(1<=ai<=10^5)

輸出
對於每個樣例，在一行輸出答案。

樣例輸入
1
2
2 3

樣例輸出
1

 

 

題目分析：先預處理處1e5的莫比烏斯函數，因為mob[i]=1表示i是偶數個素因子的乘積，mob[i]=-1表示i是奇數個素因子的乘積，mob[i]=0表示其他
回到這道題上，首先對於總的集合我任意取出兩個數的情況數為C(n,2)即 n * (n - 1) / 2，然後依次減去不滿足的情況，即gcd為2的gcd為3的，這裡就出問題了，因為如果gcd為6，那就被減了兩次，所以要容斥一下，即拿總的情況－gcd只由一個素因子構成的情況＋gcd只有兩個素因子構成的情況。。。對於每個gcd值的集合我們可以用一個num數組記錄。然後就可以看出莫比烏斯函數的強大了，容斥時對應的正負號其實就是mob數組，比如計算gcd為2的集合時，mob[2]==-1，因此減去 num[2] * (num[2] - 1) / 2，3的時候也是減，6的時候則是加，正好與mob函數的定義吻合

注：因為莫比烏斯函數是積性函數，因此可以用線性篩求得

 

 

#include 
#include 
#include 
#define ll long long
using namespace std;
int const MAX = 1e5 + 5;
int p[MAX], cnt[MAX], num[MAX], mob[MAX];
bool prime[MAX];
int pnum, ma, n;

void Mobius()   //求解莫比烏斯函數
{
    pnum = 0;
    mob[1] = 1;
    memset(prime, true, sizeof(prime));
    for(int i = 2; i < MAX; i++)
    {
        if(prime[i])
        {
            p[pnum ++] = i;
            mob[i] = -1;
        }
        for(int j = 0; j < pnum && i * p[j] < MAX; j++)
        {
            prime[i * p[j]] = false;
            if(i % p[j] == 0)
            {
                mob[i * p[j]] = 0;
                break;
            }
            mob[i * p[j]] = -mob[i];
        }
    }
}

ll cal()
{
    ll ans = (ll) n * (n - 1) / 2;
    for(int i = 2; i <= ma ; i++)
    {
        num[i] = 0;
        for(int j = i; j <= ma; j += i)
            num[i] += cnt[j];   //得到gcd為i的集合的元素個數
    }   
    for(int i = 2; i <= ma; i++)
        ans += (ll) mob[i] * num[i] * (num[i] - 1) / 2;
    return ans;
}

int main()
{   
    Mobius();
    int T;
    scanf(%d, &T);
    while(T--)
    {
        memset(cnt, 0, sizeof(cnt));
        ma = 0;
        scanf(%d, &n);
        for(int i = 0; i < n; i ++)
        {
            int tmp;
            scanf(%d, &tmp);
            cnt[tmp] ++;
            ma = max(ma, tmp);
        }
        printf(%I64d
, cal());
    }
}