当前位置:网站首页>Mathematical knowledge: divisible number inclusion exclusion principle
Mathematical knowledge: divisible number inclusion exclusion principle
2022-07-03 01:27:00 【Fight! Sao Nian!】
subject :AcWing 890. The number divisible
Given an integer n and m A different prime number p1,p2,…,pm.
Please find out 1∼n Middle energy quilt p1,p2,…,pm How many integers are divided by at least one number in .
Input format
The first line contains integers n and m.
The second line contains m A prime number .
Output format
Output an integer , Represents the number of integers that satisfy the condition .
Data range
1≤m≤16,
1≤n,pi≤109
sample input :
10 2
2 3
sample output :
7
Topic analysis :
This question uses Principle of tolerance and exclusion
First of all, it can be used m Division of different prime numbers , Then maybe there will be 1、2、3… m Circumstances .
We use binary numbers to enumerate all cases
use S1 Represents the number of sets that can only be divided by one number ,S2 The number of sets that can be divided by two numbers …
According to the principle of inclusion and exclusion, all cases are set with odd number minus even number .
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 20;
int p[N];
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++) // Enumerate all the situations
{
int t=1,s=0; // t Represents the product of numbers that can be divisible ,s The number of numbers
for(int j=0;j<m;j++)
{
if(i>>j&1) // If selected
{
if((LL)t*p[j]>n) // If the selected number is greater than n
{
t=-1;
break;
}
t *= p[j];
s++;
}
}
if(t!=-1)
{
if(s%2)res+=n/t; // Odd plus
else res-=n/t; // Even minus
}
}
cout<<res<<endl;
return 0;
}
边栏推荐
- 一位苦逼程序员的找工作经历
- Draw love with go+ to express love to her beloved
- Delete duplicate elements in the ordered linked list -ii
- Do not log in or log in to solve the problem that the Oracle database account is locked.
- Leetcode 6103 - minimum fraction to delete an edge from the tree
- Swiftui component Encyclopedia: using scenekit and swiftui to build interactive 3D pie charts (tutorial with source code)
- 力扣 204. 计数质数
- MySQL basics 03 introduction to MySQL types
- Meibeer company is called "Manhattan Project", and its product name is related to the atomic bomb, which has caused dissatisfaction among Japanese netizens
- 1696C. Fishingprince Plays With Array【思维题 + 中间状态 + 优化存储】
猜你喜欢
MySQL --- 数据库查询 - 条件查询
寻找标杆战友 | 百万级实时数据平台,终身免费使用
leetcode:871. Minimum refueling times [Pat has done before + maximum stacking + greed]
[flutter] icons component (fluttericon Download Icon | customize SVG icon to generate TTF font file | use the downloaded TTF icon file)
Strongly connected components of digraph
Database SQL language 02 connection query
Work experience of a hard pressed programmer
Leetcode 2097 - Legal rearrangement of pairs
Daily topic: movement of haystack
强化学习 Q-learning 实例详解
随机推荐
leetcode:871. 最低加油次数【以前pat做过 + 最大堆 +贪心】
Leetcode 6103 - minimum fraction to delete an edge from the tree
关于Fibonacci数列
[untitled]
The difference between tail -f, tail -f and tail
2022 cable crane driver examination registration and cable crane driver certificate examination
异步、邮件、定时三大任务
d,ldc構建共享庫
Top ten regular spot trading platforms 2022
机器学习术语
MySQL基础用法02
Esp32 simple speed message test of ros2 (limit frequency)
Using tensorboard to visualize the model, data and training process
Basis of information entropy
Give you an array numbers that may have duplicate element values. It was originally an array arranged in ascending order, and it was rotated once according to the above situation. Please return the sm
Matlab finds the position of a row or column in the matrix
按键精灵打怪学习-自动寻路回打怪点
C#应用程序界面开发基础——窗体控制(4)——选择类控件
Detailed explanation of Q-learning examples of reinforcement learning
C#应用程序界面开发基础——窗体控制(3)——文件类控件