无关(relationship)

[编程题]无关(relationship)

热度指数：5 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

若一个集合A内所有的元素都不是正整数N的因数，则称N与集合A无关。

给出一个含有k个元素的集合A={a1,a2,a3,...,ak}，求区间[L,R]内与A无关的正整数的个数。

保证A内的元素都是素数。

输入描述:

输入数据共两行：

第一行三个正整数L,R,k，意义如“题目描述”。

第二行k个正整数，描述集合A，保证k个正整数两两不相同。

输出描述:

输出数据共一行：

第一行一个正整数表示区间[L,R]内与集合A无关的正整数的个数

示例1

输入

1 10 4
2 3 5 7

输出

示例2

输入

2 10 4
2 3 5 7

输出

说明

对于30%的数据：1<=L<=R<=10^6

对于100%的数据：1<=L<=R<=10^18,1<=k<=20,2<=ai<=100

算法知识视频讲解

牛客35431719号

发表于 2020-07-25 23:36:43

解法一二进制枚举 #include <bits/stdc++.h> using namespace std; typedef long long ll; int a[25]; ll sum,l,r,k; int main() { cin>>l>>r> 展开全文

小琢卷不动

发表于 2021-11-24 10:13:29

首先容斥。定义与 AAA 有关的数组成的集合是无关的补集。考虑如何求有关的数的个数，由 ∣A∪B∣=∣A∣+∣B∣−∣A∩B∣|A∪B|=|A|+|B|-|A∩B|∣A∪B∣=∣A∣+∣B∣−∣A∩B∣ 可知，直接枚举所有 2k2^k2k 种情况并去掉重复的即可。考虑如何计算 L∼RL\sim 展开全文