专栏首页数据结构与算法#19. 计数(容斥原理)

#19. 计数(容斥原理)

时间限制:1s

内存限制:256MB

【问题描述】

给出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]

【输出】

输出文件名为count.out。

输出一行,包含1个整数,表示答案

【输入输出样例】

count.in

count.out

10 2 2 3

3

【数据说明】

对于60%的数据,1<=n<=106

对于另外20%的数据,m=2

对于100%的数据,1<=n<=109,0<=m<=20,1<=a[i]<=109

容斥原理

对于三个数的情况

我们需要加上每个数对答案的贡献,减去两两对答案的贡献,加上三三对答案的贡献

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<queue>
 7 #define LL long long 
 8 using namespace std;
 9 const LL MAXN=100001;
10 inline void read(LL &n)
11 {
12     char c=getchar();bool flag=0;n=0;
13     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
14     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
15 }
16 LL gcd(LL a,LL b)
17 {
18     return b==0?a:gcd(b,a%b);
19 }
20 LL ans=0;
21 LL a[MAXN];
22 LL n,m;
23 void dfs(LL now,LL num,LL how)
24 {
25     if(num>n)    return ;
26     if(now==m+1)
27     {
28         ans+=(n/num)*how;
29         return ;
30     }
31     dfs(now+1,num,how);
32     dfs(now+1,num*a[now]/(gcd(num,a[now])),-how);
33 }
34 int main()
35 {
36     read(n);read(m);
37     for(LL i=1;i<=m;i++)
38         read(a[i]);
39     dfs(1,1,1);
40     printf("%lld",ans);
41     return 0;
42 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 洛谷P1450 [HAOI2008]硬币购物

    题目描述 硬币购物一共有4种硬币。面值分别为c1,c2,c3,c4。某人去商店买东西,去了tot次。每次带di枚ci硬币,买si的价值的东西。请问每次有多少种付...

    attack
  • 洛谷P3383 【模板】线性筛素数(Miller_Rabin)

    题目描述 如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内) 输入输出格式 输入格式: 第一行包含两个正整数N、M,分别表示...

    attack
  • 51Nod 1051 最大子矩阵和

    1051 最大子矩阵和 基准时间限制:2 秒 空间限制:131072 KB 分值: 40 难度:4级算法题 一个M*N的矩阵,找到此矩阵的一个子矩阵,并且这个子...

    attack
  • 洛谷P3799 妖梦拼木棒

    题目背景 上道题中,妖梦斩了一地的木棒,现在她想要将木棒拼起来。 题目描述 有n根木棒,现在从中选4根,想要组成一个正三角形,问有几种选法? 输入输出格式 输入...

    attack
  • 1775. [国家集训队2010]小Z的袜子

    【题目描述】     作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他...

    attack
  • 轻叩次元壁——谈谈真人头像的漫画化

    在这篇自带萌点的文章中,作者提出了一种新型模型TwinGAN,可以将真人头像转化成漫画风的卡通头像。打通二次元和三次元的世界的方法,都在这里面了~

    量子位
  • 51nod1004 n^n的末位数字

    题目来源: Author Ignatius.L (Hdu 1061) 基准时间限制:1 秒 空间限制:131072 KB 分值: 5  难度:1级算法题 给出一...

    attack
  • 一样的打游戏,不一样的酷

    夏乙 问耕 假装发自 凹非寺 量子位 出品 | 公众号 QbitAI ? 假期模式已经开启了~ 学生党已经赋闲在家,工业党不少也已带着橘子返乡。 阖家欢乐,面对...

    量子位
  • 位图原理及实现 - 海量数据处理标配

    为什么要位图?上一篇里面有个例子,是这样的: 你要给1亿个int型数据去重(本篇不讲int以外的,int以外的等我学了布隆过滤器或者各位自行学习布隆过滤器之后...

    看、未来
  • python拾遗【2】自定义异常类

    用户2936342

扫码关注云+社区

领取腾讯云代金券