interval-count-12

This problem of Oz is very straight forward. You are given N distinct prime integers i.e p1, p2,..., pN and an interval [L,R]. Calculate number of integers in this interval that are divisible by at least one of the given primes.

Input : 
First line of input contain an integer T — the number of test cases. T tests follow. First line of each test case contain 3 integers — N, L, R. and the next line contains N distinct prime integers - p1, p2,..., pN.

Output :
For each test case output a single number — number of integers in [L,R], that are divisible by at least one of the given primes.

Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 10
1 < pi < 1000 where i=1,2..N 
1 ≤ L ≤ R ≤ 10^18

SAMPLE INPUT
2
1 1 10
3
2 1 10
2 3

SAMPLE OUTPUT
3
7

Explanation

For second sample : 
Numbers in the interval [1,10] which are divisible by at least one prime from (2,3) are as follow :
2, 3, 4, 6, 8, 9, 10

Source: hackerearth | Difficulty: EASY
Tags: Number theory

Mathematics


Solutions:
T=int(input())
for i in range(T):
	N,L,R=list(map(int, input().split()))
	arrP=list(map(int, input().split()))
	bits=[[] for _ in range(N+1)]
	for i in range(1,pow(2,N)):
		bits[bin(i).count("1")].append(i)
	# calc for L-1, R inclusive from 1:
	numL=0
	numR=0
	muls=[1]
	sign=1
	for i in range(N):
		for num in bits[i+1]:
			k=1
			for j in range(N):
				if num&(1<<j):
					k*=arrP[j]
			if k<=R:
				numL+=sign*((L-1)/k)
				numR+=sign*(R/k)
		sign=-sign
	print(numR-numL)