学步园

题目链接：Click here~~

题意：

给你一个集合M，里面最多有10个非负数，问1~n-1中一共有多少个数可以被其中一个整除。

解题思路：

比较简单的容斥吧，可惜我WA了一个下午。

很容易的想到，ans = sum{ 整除一个的数 } - sum{ 整除两个的数 } + sum{ 整除三个的数 } - …… 。

而整除 k 个数的数可以表示成 lcm(A1,A2,…,Ak) 的倍数的形式。

而我的错误出在哪里了呢？

就是思维定势，直接套了上次那个程序，结果发现有一个剪枝条件在这里是不适用的。

假设b<c，则如果lcm(a,b)大于x，lcm(a,c)不一定大于x。

这算是本题的一个收获吧，另外，我把dfs的参数也弄少了，看着清爽了些。

#include <stdio.h>
#include <algorithm>

using namespace std;

typedef __int64 LL;

int fac[12],top,ans,n;

int gcd(int a,int b)
{
    return b ? gcd(b,a%b) : a;
}

int lcm(int a,int b)
{
    return a/gcd(a,b)*b;
}

void dfs(int i,int cnt,int num,int m)
{
    if(cnt == m)
    {
        int sum = (n-1)/num;
        m&1 ? ans += sum : ans -= sum;
        return ;
    }
    if(top-i < m-cnt)
        return ;
    int LCM = lcm(num,fac[i]);
    if(LCM <= n-1)
        dfs(i+1,cnt+1,LCM,m);
    dfs(i+1,cnt,num,m);
}

int sovle()
{
    ans = 0;
    for(int m=1;m<=top;m++)
        dfs(0,0,1,m);
    return ans;
}

int main()
{
    while(~scanf("%d%d",&n,&top))
    {
        for(int i=0;i<top;i++)
        {
            scanf("%d",&fac[i]);
            if(!fac[i])
                i--,top--;
        }
        printf("%d\n",sovle());
    }
    return 0;
}