当前位置:网站首页>Inclusion exclusion principle acwing 890 Divisible number
Inclusion exclusion principle acwing 890 Divisible number
2022-07-05 06:24:00 【T_ Y_ F666】
Principle of tolerance and exclusion AcWing 890. The number divisible
Original link
AcWing 890. The number divisible
Algorithm tags
Principle of tolerance and exclusion
Ideas
Code
#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;
// Enumerate from 1 To 1111...(m individual 1) Every set state of , ( Select at least one set )
rep(i, 1, 1<<m){
// t Represents the product of prime numbers cnt Indicates the number of current selection sets
int t=1, cnt=0;
rep(j, 0, m){
if(i>>j&1){
// The product is greater than n, be n/t = 0, Jump out of this cycle
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);
}
Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support
边栏推荐
- ADG5412FBRUZ-RL7应用 双电源模拟开关和多路复用器IC
- MPLS experiment
- [rust notes] 17 concurrent (Part 2)
- Gaussian elimination acwing 884 Gauss elimination for solving XOR linear equations
- 中国剩余定理 AcWing 204. 表达整数的奇怪方式
- 阿里新成员「瓴羊」正式亮相,由阿里副总裁朋新宇带队,集结多个核心部门技术团队
- LeetCode-61
- Bit of MySQL_ OR、BIT_ Count function
- One question per day 1020 Number of enclaves
- ollvm编译出现的问题纪录
猜你喜欢
Bit of MySQL_ OR、BIT_ Count function
ollvm编译出现的问题纪录
Doing SQL performance optimization is really eye-catching
MatrixDB v4.5.0 重磅发布,全新推出 MARS2 存储引擎!
Navicat连接Oracle数据库报错ORA-28547或ORA-03135
20220213-CTF MISC-a_ good_ Idea (use of stegsolve tool) -2017_ Dating_ in_ Singapore
阿里新成员「瓴羊」正式亮相,由阿里副总裁朋新宇带队,集结多个核心部门技术团队
3.Oracle-控制文件的管理
Gauss Cancellation acwing 884. Solution d'un système d'équations Xor linéaires par élimination gaussienne
什么是套接字?Socket基本介绍
随机推荐
Client use of Argo CD installation
5.Oracle-表空间
Regulations for network security events of vocational group in 2022 Guizhou Vocational College skill competition
Redis-01.初识Redis
Golang uses context gracefully
容斥原理 AcWing 890. 能被整除的数
How to make water ripple effect? This wave of water ripple effect pulls full of retro feeling
MatrixDB v4.5.0 重磅发布,全新推出 MARS2 存储引擎!
快速使用Amazon MemoryDB并构建你专属的Redis内存数据库
[2021]GIRAFFE: Representing Scenes as Compositional Generative Neural Feature Fields
MySQL advanced part 2: SQL optimization
Leetcode-1200: minimum absolute difference
高斯消元 AcWing 884. 高斯消元解异或线性方程组
Leetcode-6110: number of incremental paths in the grid graph
Leetcode-31: next spread
Sqlmap tutorial (1)
our solution
Basic explanation of typescript
[rust notes] 15 string and text (Part 1)
Doing SQL performance optimization is really eye-catching