题目描述
给出m个数a[1],a[2],…,a[m]
求1~n中有多少数不是a[1],a[2],…,a[m]的倍数。
输入输出格式
输入格式：
输入文件名为count.in。
第一行，包含两个整数：n,m
第二行，包含m个数，表示a[1],a[2],…,a[m]
输出格式：
输入输出样例
输入样例#1：
count.in count.out 10 2 2 3 3
输出样例#1：
输出一行，包含1个整数，表示答案
说明
对于60%的数据，1<=n<=106
对于另外20%的数据，m=2
对于100%的数据，1<=n<=109,0<=m<=20,1<=a[i]<=109
补几发题解
容斥，奇数个数的|lcm|减去，偶数个的加上
#include<cstdio> using namespace std; #define LL long long int a[40]; int n,m; int gcd(int x,int y) { if(y==0)return x; else return gcd(y,x%y); } LL ans=0; void dfs(int num,int step,LL lcm) { if(lcm>n)return ; if(num==m+1){ if(step%2==1)ans-=n/lcm;//奇数个时加上 else if(step)ans+=n/lcm;//偶数个时减去 return ; } dfs(num+1,step,lcm); LL tmp=lcm*a[num]/gcd(lcm,a[num]);//选择该数 dfs(num+1,step+1,tmp); } int main () { scanf("%d%d",&n,&m); ans=n; for(int i=1;i<=m;++i ) { scanf("%d",a+i); } dfs(1,0,1); printf("%lld ",ans); return 0; }