数论 - 容斥原理

一、题目描述

能被整除的数

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

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

输入格式

第一行包含整数 n 和 m。

第二行包含 m 个质数。

输出格式

输出一个整数，表示满足条件的整数的个数。

数据范围

1≤m≤16,
1≤n,pi≤10⁹

输入样例：

10 2
2 3

输出样例：

7

二、算法思路

三、代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 20;

int p[N];

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i ++ ) cin >> p[i];

    int res = 0; //答案
    for (int i = 1; i < 1 << m; i ++ ) //1 << m是2的m次方
    {
        int t = 1, s = 0; //t表示该二进制选择情况的约数，s表示该约数有多少个1
        for (int j = 0; j < m; j ++ )
            if (i >> j & 1)
            {
                if ((LL)t * p[j] > n) //约数大于被约束不成立
                {
                    t = -1;
                    break;
                }
                t *= p[j];
                s ++ ;
            }

        if (t != -1)
        {
	        //通过1个数来判断正负号
            if (s % 2) res += n / t;
            else res -= n / t;
        }
    }

    cout << res << endl;

    return 0;
}