当前位置:网站首页>容斥原理 AcWing 890. 能被整除的数
容斥原理 AcWing 890. 能被整除的数
2022-07-05 06:16:00 【T_Y_F666】
容斥原理 AcWing 890. 能被整除的数
原题链接
算法标签
容斥原理
思路
代码
#include<bits/stdc++.h>
#define int long long
#define abs fabs
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 20;
int a[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void put(int x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) put(x/10);
putchar(x%10^48);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n=read(), m=read();
rep(i, 0, m){
a[i]=read();
}
int res=0;
// 枚举从1 到 1111...(m个1)的每一个集合状态, (至少选中一个集合)
rep(i, 1, 1<<m){
// t表示质数乘积 cnt表示当前选法集合数量
int t=1, cnt=0;
rep(j, 0, m){
if(i>>j&1){
// 乘积大于n, 则n/t = 0, 跳出这轮循环
if(t*a[j]>n){
t=-1;
break;
}
cnt++;
t*=a[j];
}
}
if(t!=-1){
if(cnt%2){
res+=n/t;
}else{
res-=n/t;
}
}
}
printf("%lld", res);
}
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈
边栏推荐
猜你喜欢
Simple selection sort of selection sort
NotImplementedError: Cannot convert a symbolic Tensor (yolo_boxes_0/meshgrid/Size_1:0) to a numpy ar
数据可视化图表总结(二)
RGB LED infinite mirror controlled by Arduino
SPI 详解
MySQL怎么运行的系列(八)14张图说明白MySQL事务原子性和undo日志原理
阿里新成员「瓴羊」正式亮相,由阿里副总裁朋新宇带队,集结多个核心部门技术团队
LeetCode 0108. Convert an ordered array into a binary search tree - the median of the array is the root, and the left and right of the median are the left and right subtrees respectively
QQ computer version cancels escape character input expression
Matrixdb V4.5.0 was launched with a new mars2 storage engine!
随机推荐
liunx启动redis
[rust notes] 16 input and output (Part 2)
Leetcode-9: palindromes
CPU内核和逻辑处理器的区别
Niu Mei's math problems
1.15 - 输入输出系统
1.14 - assembly line
Appium automation test foundation - Summary of appium test environment construction
Quickly use Amazon memorydb and build your own redis memory database
Is it impossible for lamda to wake up?
How to generate an image from text on fly at runtime
[BMZCTF-pwn] ectf-2014 seddit
Règlement sur la sécurité des réseaux dans les écoles professionnelles secondaires du concours de compétences des écoles professionnelles de la province de Guizhou en 2022
MySQL advanced part 2: the use of indexes
Navicat連接Oracle數據庫報錯ORA-28547或ORA-03135
可变电阻器概述——结构、工作和不同应用
In depth analysis of for (VaR I = 0; I < 5; i++) {settimeout (() => console.log (I), 1000)}
Leetcode-31: next spread
快速使用Amazon MemoryDB并构建你专属的Redis内存数据库
leetcode-6109:知道秘密的人数