能被整除的数

题意

给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。

请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。

思路

容斥原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>

using namespace std;
long long p[23],n,m;

int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++) cin>>p[i];
    
    long long res=0;
    
    for(int i=1;i<1<<m;i++){
        long long t=1,cnt=0;
        for(int j=0;j<m;j++){
            if(i>>j&1){
                if(t*p[j]>n){
                    t=-1;
                    break;
                }
                cnt++;
                t*=p[j];
            }
            
        }
        if(t!=-1){
            if(cnt%2){
                res+=(n/t);
            }else{
                res-=(n/t);
            }
        }
    }
    cout<<res;
    
}

技巧总结：注意记住是怎么写的

Devu和鲜花

题意

N 个盒子，第 i 个盒子中有 Ai 枝花。

同一个盒子内的花颜色相同，不同盒子内的花颜色不同。

要从这些盒子中选出 M 枝花组成一束，求共有多少种方案。

若两束花每种颜色的花的数量都相同，则认为这两束花是相同的方案。

思路

理想每一组中可以取无限朵花，那么我们就需要达到x1+x2+x3+……+xn=M。

用隔板法，为$C_{M+N-1}^{N-1}$

那么正难则反，考虑求补集，也就是至少不满足其中一个条件的方案。就可以用总方案减去这些方案就可以得出答案。若第i个盒子超过了ai支，则不满足，设不满足 i 的方案为 si ，答案就要用到容斥原理了。

考虑si怎么求。以s1举例，假如要求s1，就代表我们必须从第一组里取出至少A1+1朵花，那么此时还剩M−(A1+1)朵花。剩下的就是隔板，那么此时方案为$C_{M+N-1-(A1+1)}^{N-1}$

注意因为在处理的时候为了使用隔板法，已经将每个数都加1，变成大于1的数，所以这里的先拿出a1 + 2 朵花其实是至少拿 ai + 1 朵花

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <deque>

using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const int N=1010,mod=1e9+7;
LL down=1,n,m;
LL A[21];
LL res,ans;
int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int C(LL a, LL b)
{
    if (a < b) return 0;
    int up = 1;
    for (LL i = a; i > a - b; i -- ) up = i % mod * up % mod;
    return (LL)up * down % mod;
}

int main(){
    
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<n;i++) scanf("%lld",&A[i]);
    for(int i=2;i<=n-1;i++) down = down*qmi(i,mod - 2,mod)%mod;
    

    res=0;
    for(int i =0;i<1<<n;i++){
        LL x = m+n-1,y=n-1;
        int sign=1;
        for(int j=0;j<n;j++){
            if(i>>j&1){
                sign*=-1;
                x -= A[j]+1;
                if(x<0) break;
            }
        }
        res = (res+C(x,y)*sign)%mod;
    }

    cout<<(res+mod)%mod<<endl;
    return 0;
}

总结