题目描述

注释版，仅记录。

算法1

C++ 代码

#include<cstdio>
#include<cstring>
#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++)     //位运算枚举所有集合的情况
    {
        int t=1,s=0;    //t表示当前质数的乘积，s表示位数
        for(int j=0;j<m;j++)    //枚举每一位
        {
            if(i>>j & 1)        //选第j+1个集合
            {
                if((LL)t * p[j]>n)
                {
                    t=-1;
                    break;
                }
                t*=p[j];
                s++;
            }
        }

        if(t != -1)     //奇数为加，偶数为减
        {
            if(s%2) res+=n/t;
            else res-=n/t;
        }
    }

    cout<<res<<endl;

    return 0;
}