POJ 3904 Sky Code 容斥原理

Description

给出数字N，给出N个数字，从中找出四个数字，它们的公因数只有“1”，问能找到多少组？

Analyze

测试四个数字的公因数是否只有“1”并不好实现，要检测多次。

试着从 (是 = 总 - 非) 方面想

对每个数字进行①质因数分解(准公因子)

同时记录下②不同质因子之间相乘所构成的重公因子

统计所有③准公因子与重公因子出现的次数（假设为num[i]）

计算④组合数C(num[i], 4) 即为以num[i]为公因子的四个数的组合数目

但是在这里面，计算2、3、6会有重复，于是便有了容斥

Code

#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll __int64

int factor[10005], cnt = 0;
map<int, int> Count;
map<int, int> Num;

void get_factors(int n)
{
    cnt = 0;
    for(int i = 2; i * i <= n; ++i)
    {
        if(n % i == 0)
        {
            factor[cnt++] = i;
            while(n % i == 0)
                n /= i;
        }
    }
    if(n != 1)
        factor[cnt++] = n;
}

void Rongchi(int n)///队列版
{
    get_factors(n);
    int t = 0, q[10005], flag[10005];
    q[t++] = 1;
    memset(flag, -1, sizeof(flag));
    for(int i = 0; i < cnt; ++i)
    {
        int up = t;
        for(int j = 0; j < up; ++j)///一层循环一种集合
        {
            q[t] = q[j] * factor[i];
            Count[ q[t] ]++;
            flag[t] = -flag[j];
            Num[ q[t] ] = (flag[t] == 1 ? 1 : 0);
            t++;
        }
    }
}

void Rongchi(int n)///二进制版
{
    get_factors(n);
    for(int i = 1; i < (1 << cnt); ++i)///一层循环一种集合
    {
        int tem = 1, tot = 0;
        for(int j = 0; j < cnt; ++j)
            if(i & (1 << j))
            {
                tot++;
                tem *= factor[j];
            }
        Count[tem]++;
        Num[tem] = tot;
    }
}

///num : 当前针对第几个元素
///used : 在此之前拿取了多少个元素
///up : 目标是取几个元素
///mu : 已取元素之积

void DFS(int num, int used, int up, int mu)
{
    if(used == up)
    {
        Count[mu]++;
        if(up & 1)
            Num[mu] = 1;
        else
            Num[mu] = 0;
        return;
    }
    if(num == cnt)
        return ;
    DFS(num + 1, used, up, mu);
    DFS(num + 1, used + 1, up, mu * factor[num]);
}

void Rongchi(int n)///DFS版
{
    get_factors(n);
    int mu = 1;
    for(int i = 1; i <= cnt; ++i)///子集内含有的元素个数(实现奇加偶减)
        DFS(0, 0, i, 1);
}

ll C(ll n)///这里n虽不到10000,若用int,n^4会爆
{
    return n * (n - 1) * (n - 2) * (n - 3) / 24;
}

int main()
{
    int n, a;
    while(~scanf("%d", &n))
    {
        Count.clear();
        for(int i = 0; i < n; ++i)
        {
            scanf("%d", &a);
            Rongchi(a);
        }
        ll ans = 0;
        map<int, int> ::iterator it = Count.begin();
        for(; it != Count.end(); ++it)
        {
            int idx = it -> first;
            if(Num[idx] & 1)
                ans += C(Count[idx]);
            else
                ans -= C(Count[idx]);
        }
        cout << C(n) - ans << '\n';
    }
    return 0;
}

实现容斥的三种模板

①队列式

巧妙地运用了负负得正来决定奇加偶减

②二进制

巧妙地运用了一个n元集合有 2 ^ n 个子集的性质，去掉空集从1开始，保留全集到2 ^ n结束，对这2 ^ n个数，以一个自增计数器 i 的每个二进制形式决定每个集合的构成。从 i 的二进制形式的右边向左边看，第 j 位上有1表示当前集合含有全集里的第 j 个元素，那么i的二进制里1的个数自然而然地反映了当集合内的元素个数，实现奇加偶减

③.DFS

直接对子集中含有元素的个数进行枚举，可根据自增变量实现奇加偶减