时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld
题目描述
给出一个集合和一个数m。
集合里面有n个质数。
请你求出从 1 到 m 的所有数中,至少能被集合中的一个数整除的数的个数。
输入描述:
第一行两个正整数 n 和 m 。第二行n个正整数,分别为集合中的质数。
输出描述:∑
输出一个整数,表示符合要求的正整数的个数。
示例1
输入
3 37
5 7 13
输出
13
备注:
对于100%的数据,有n<=20,m为有符号64位正整数,集合内质数<=1000000000分析:容斥原理。想起了概率论加法公式的推广:
#include <cstdio>
#include <algorithm>
using namespace std;
long long ans,N,M,a[30];
void dfs(int k,int sum,long long cur)
{
if(k==N) return;
if(a[k]<=M/cur)
{
ans=ans+sum*M/(cur*a[k]);
dfs(k+1,sum,cur);
dfs(k+1,-sum,cur*a[k]);
}
else return;
}
int main()
{
scanf("%lld%lld",&N,&M);
for(int i=0;i<N;i++)
scanf("%lld",&a[i]);
sort(a,a+N);
dfs(0,1,1);
printf("%lld",ans);
return 0;
}
View Code
原文链接: https://www.cnblogs.com/ACRykl/p/8068173.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/266189
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!