Handsome Numbers
You will be given two lists of cardinals - list D and list ND. For some integer num, we will say that num is handsome number if it is divisible by at least one number from D and not divisible by at least one number from ND.
If you are given integers A and B, find how many integers in interval [ A, B ] are handsome numbers.
InputFirst line of the standard input will contain integers n1 (1 <= n1 <= 16), n2 (1 <= n2 <= 1 000), A and B (0 <= A <= B <= 10<sup>18</sup>), where n1 represents length of the list D and n2 represents length of the list ND.
Next n1 lines will contain integers from the list D.
Next n2 lines will contain integers from the list ND.
Integer from the lists D and ND will be from interval [1, 1 000 000].
Next n1 lines will contain integers from the list D.
Next n2 lines will contain integers from the list ND.
Integer from the lists D and ND will be from interval [1, 1 000 000].
OutputOn standard output you should print how many handsome numbers are in interval [ A, B ].
Input:
Output:
Explanation:
Handsome numbers are:
4, 5, 6, 8, 10, 14, 15, 16, 18, 20.
Note that number 12 is divisible by at least one number from D, but there is no any number from ND with which is not divisible.
2 2 3 20
2
5
3
4Output:
10Explanation:
Handsome numbers are:
4, 5, 6, 8, 10, 14, 15, 16, 18, 20.
Note that number 12 is divisible by at least one number from D, but there is no any number from ND with which is not divisible.
Input:
Output:
5 7 345 7845
3
6
2
7
11
19
22
10
20
30
5
4Output:
5551Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.