首页 > 试题广场 >

无关(relationship)

[编程题]无关(relationship)

若一个集合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

算法知识视频讲解

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

容斥原理与鸽巢原理

难度：

0条回答 0收藏 4浏览

查看代码

无关(relationship)

扫一扫，把题目装进口袋