AcWing 890 能被整除的数
发布日期:2021-05-28 16:27:13 浏览次数:8 分类:技术文章

本文共 1182 字,大约阅读时间需要 3 分钟。

题目描述:

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

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

输入格式

第一行包含整数n和m。第二行包含m个质数。

输出格式

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

数据范围

1≤m≤16,

1≤n,pi≤10^9

输入样例:

10 22 3

输出样例:

7

分析:

本题考察容斥原理。即。通俗的说,就是求n个集合的并集,需要先将n个集合加起来,然后减去所有两个集合的交集,在加上所有三个集合的交集,...。这样交替加减下去就得到了n个集合的并集了。题目要求1-n中能被至少给定质数中一个整除数的个数。比如n = 10,给定p = 2,3.能被2整除的数有2,4,6,8,10;能被3整除的数有3 6 9;能被2,3同时整除的数有6,故一共有5 + 3 - 1 = 7个数。而1到n中能被p整除数的个数为n / p,问题仅在于给定m个质数,如何从中选出需要的若干个数。

从m个质数中选数使用了在状态压缩中常用的位运算操作,1到2^m - 1对应了所有数的选择情况,对应位为1表示选中了,对应位为0表示未选中。比如m = 5,数21 = 10101表示选中了第1,3,5个质数。用此方式确定选中的质数及其乘积,当被选中的质数个数是奇数时,我们就加上1到n中能被这些数乘积整除的数的个数;是偶数时就减去能被这些数整除数的个数。

#include 
using namespace std;typedef long long ll;int p[20];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; 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){ if(s % 2) res += n / t; else res -= n / t; } } cout<
<

 

转载地址:https://blog.csdn.net/qq_30277239/article/details/103822542 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:AcWing 891 Nim游戏
下一篇:AcWing 889 满足条件的01序列

发表评论

最新留言

感谢大佬
[***.8.128.20]2024年02月02日 10时41分14秒