摘要
Title: 890. 能被整除的数
Tag: 容斥、二进制枚举
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

890. 能被整除的数

• 题意

  给定一个整数 n 和 m 个不同的质数 p1,p2,…,pm。
  请你求出 1∼n 中能被 p1,p2,…,pm 中的至少一个数整除的整数有多少个。

• 思路

  枚举$2^m$个集合，复杂度$O(m2^m)$

  • 枚举所有集合的操作，可以用二进制枚举实现
  • 利用容斥原理，当集合数量为奇数时，加上；为偶数时，减去

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-13 12:29:37
  FilePath: \ACM\Acwing\890.py
  LastEditTime: 2022-03-13 14:15:50
  '''
  n, m = map(int, input().split())
  nums = list(map(int, input().split()))
  
  ans = 0
  for i in range(1, 1 << m):
      cnt, prob = 0, 1
      for j in range(m):
          if i >> j & 1:
              cnt += 1
              prob *= nums[j]
      if cnt & 1: 
          ans += n // prob
      else:
          ans -= n // prob
  
  print(ans)