Mehta is a very rich guy. He has $N$ types of coins, and each type of coin is available in an unlimited supply.  

So Mehta goes to a supermarket to buy monthly groceries. There he sees that every item has a unique price, that is, no two items have the same price.  

Now, the supermarket owner tells Mehta that they are selling items in the price range $[L,R]$ only on that particular day. He also tells Mehta that for every price, there is an item in the shop.  

The supermarket has recently adopted a weird new tradition: Mehta may only use a single type of coin for each item he purchases. For example, he could pay for an item of price 4 with two 2-coins, but not with a 3-coin and a 1-coin.  

As you know Mehta is very weak at calculations, so he wants you to do these calculations for him and tell how many different types of items he can buy.  

Input Format 

The first line of input contains $N$, the number of types of coins Mehta has. 

Then the next $N$ lines contain an integer each: the i^{th} line contains $A[i]$, the value of Mehta's i^{th} type of coin.  

Then the next line contains a number $\mbox{D}$, the number of days Mehta goes shopping. 

Then each of the next $\mbox{D}$ lines contains numbers $\boldsymbol{\mbox{L}}$ and $\mbox{R}$, denoting that they are selling items in price range $[L,R]$ on that particular day.  

Output format 

There will be $\mbox{D}$ lines, each containing the number of distinct items that can be bought at that particular day.  

Constraints 

$1\leq N\leq17$ 

$1\leq A[i]\leq51$ 

$1\leq D\leq101$ 

$1\leq L\leq R\leq10^{18}$  

Sample Input  

4
2
3
4
5
3
1 10
2 20
3 7

Sample output

8
14
4

Explanation 

For $L=1$ and $R=10$ you can buy items of price $\{2,3,4,5,6,8,9,10\}$. 

For $L=2$ and $\textbf{R}=20$ you can buy items of price $\text{{2,3,4,5,6,8,9,10,12,14,15,16,18,20}}$. 

For $L=3$ and $R=7$ you can buy items of price $\{3,4,5,6\}$.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Combinatorics


Solutions:
import itertools, math, fractions

def findsubsets(S, m):
	return set(itertools.combinations(S, m))

def createInitial():
	l = [int(input()) for i in range(int(input()))]
	ln = list()
	for x in range(len(l)):
		yes = 1
		for y in range(x):
			if l[x] % l[y] == 0:
				yes = 0
		if yes == 1:
			ln.append(l[x])
	return ln

def createBig():
	big = list()
	big.append(list)
	big[0] = l
	for i in range(2, len(l) + 1):
		big.append(list())
		temp = list()
		ans = findsubsets(l, i)
		for vals in ans:
			v = 1
			for x in range(len(vals)):
				v = v * vals[x] // fractions.gcd(v, vals[x])
			temp.append(v)
		temp.sort()
		big[i - 1] = temp
	return big
l = createInitial()
b = createBig()
for i in range(int(input())):
	r = list(map(int, input().split()))
	low = r[0]
	high = r[1]
	counter = 0
	for x in range(len(b)):
		change = 0
		for y in range(len(b[x])):
			val = b[x][y]
			operator = 0
			if x % 2 == 0:
				operator = 1
			else:
				operator = -1
			lower = math.ceil(low // val)
			upper = high // val
			diff = upper - lower
			if low % val == 0:
				diff += 1
			if operator == 1:
				change += diff
			else:
				change -= diff
		counter += change
	print(counter)


import functools, fractions

def lcm(x, y):
	return x * y // fractions.gcd(x, y)

def all_mults(nlist):
	divs = []
	divs.append([nlist[0]])
	for i in range(1, len(nlist)):
		divs.append([functools.reduce(lcm, nlist[:i + 1])])
		for j in range(i - 1, 0, -1):
			divs[j].extend([lcm(nlist[i], k) for k in divs[j - 1]])
		divs[0].append(nlist[i])
	return divs

def supermarket(n, l):
	sign = 1
	res = 0
	for i in l:
		tsum = sum([n // j for j in i])
		res += sign * tsum
		sign = -sign
	return res
n = int(input())
alist = [0] * n
for i in range(n):
	alist[i] = int(input())
alist.sort()
d = int(input())
if alist[0] == 1:
	for i in range(d):
		(l, r) = map(int, input().strip().split())
		print(r - l + 1)
else:
	flist = all_mults(alist)
	for i in range(d):
		(l, r) = map(int, input().strip().split())
		print(supermarket(r, flist) - supermarket(l - 1, flist))


import math

def lcm(F):
	lcmFactors = dict(F[0])
	for f in F[1:]:
		for (n, c) in f.items():
			lcmFactors[n] = max(lcmFactors.get(n, 0), c)
	result = 1
	for (n, c) in lcmFactors.items():
		result *= n ** c
	return result

def factorize(N):
	F = dict()
	while N > 1:
		if N % 2 == 0:
			F[2] = F.get(2, 0) + 1
			N = N // 2
		else:
			for x in range(3, int(math.sqrt(N) + 1), 2):
				if N % x == 0:
					F[x] = F.get(x, 0) + 1
					N = N // x
					break
			else:
				F[N] = F.get(N, 0) + 1
				N = 1
	return F

def f(A, R, F):
	total = 0
	for n in range(1, 2 ** len(A)):
		t = n
		multiplier = -1
		divisor = 1
		factorList = list()
		for i in range(0, len(A)):
			if t & 1:
				factorList.append(F[i])
				multiplier *= -1
			t = t >> 1
			if not t:
				break
		divisor = lcm(factorList)
		common = R // divisor
		total += common * multiplier
	return total

def solve(A, L, R):
	divisors = list()
	factors = list()
	for x in sorted(A):
		for d in divisors:
			if x % d == 0:
				break
		else:
			divisors.append(x)
			factors.append(factorize(x))
	return f(divisors, R, factors) - f(divisors, L - 1, factors)
A = list()
for _ in range(0, int(input())):
	A.append(int(input()))
for _ in range(0, int(input())):
	print(solve(A, *[int(x) for x in input().split(' ')]))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return b // gcd(a, b) * a

def number_of_items(x, a):
	if len(a) == 0:
		return 0
	n = len(a)
	k = []
	for i in range(n):
		k.append([])
	sum = 0
	for i in range(n):
		ai = a[i]
		res = x // ai
		sum += res - number_of_items(res, k[i])
		for j in range(i + 1, n):
			mygcd = ai // gcd(ai, a[j])
			k[j].append(mygcd)
	return sum
n = int(input())
a = []
for i in range(n):
	ai = int(input())
	a.append(ai)
a = sorted(a, reverse=True)
b = []
for i in range(n):
	flag = True
	for j in range(i + 1, n):
		if a[i] % a[j] == 0:
			flag = False
			break
	if flag:
		b.append(a[i])
b.reverse()
d = int(input())
l = []
r = []
for i in range(d):
	(li, ri) = [int(item) for item in input().strip().split()]
	print(number_of_items(ri, b) - number_of_items(li - 1, b))


from sys import stdin
from itertools import accumulate as acc, count, combinations_with_replacement as cmbrep, takewhile as tkw, repeat as rp, dropwhile as dpw, combinations as comb
from functools import reduce
from random import randint
from collections import Counter
from math import sqrt, log
from fractions import gcd
from heapq import merge
from os.path import basename, exists, expanduser, splitext, isfile
from os import getcwd
lolPath = getcwd()
randid = '\\qosdjfoiz.txt'
home = isfile(lolPath + randid)
if home:
	filou = 'D:\\ZeDaddy\\Documents\\Hack\\combinatorics\\supMktIn12.txt'
else:
	filou = None
if home:
	from mesures import ch, prof
trace = 0
prof = 0
tst = 0

def lcm(S):
	if len(S) == 1:
		return S[0]
	l = lcm(S[1:])
	return S[0] * l // gcd(S[0], l)

def lesserStupSubntr(R):
	(res, sgn) = (0, 1)
	for tb in TCO:
		for l in tkw(lambda v: v <= R, tb):
			res += sgn * (R // l)
		sgn = -sgn
	return res

def prep(A):
	r = []
	for a in A:
		for b in A:
			if b < a and a % b == 0:
				break
		else:
			r += [a]
	(A, r) = (r, [])
	for l in range(len(A)):
		rt = []
		for co in comb(A, l + 1):
			lc = lcm(co)
			if lc <= 10 ** 18:
				rt += [lc]
		r += [sorted(rt)]
	return (A, r)

def lessStup(L, R):
	return lessStupSub(R) - lessStupSub(L - 1)
rd = open(filou) if filou else stdin
A = [int(rd.readline().strip()) for _ in range(int(rd.readline().strip()))]
if home:
	cr = ch()
(A, TCO) = prep(A)
if home:
	print('prep en', cr.lap())
for _ in range(int(rd.readline().strip())):
	(L, R) = list(map(int, rd.readline().strip().split()))
	lessStupSub = lesserStupSubntr
	print(lessStup(L, R))
if home:
	print(cr.lap())


from fractions import gcd

def lcm(a, b):
	return a * b // gcd(a, b)
N = int(input())
C = [int(input()) for i in range(N)]
D = int(input())
C.sort()
for i in range(N - 1):
	c = C[i]
	if not c:
		continue
	for j in range(i + 1, N):
		if not C[j] % c:
			C[j] = 0
C = [c for c in C if c]

def combine(seq, c):
	size = len(seq)
	ext = [None] * (size + 1)
	for (i, (m, p)) in enumerate(seq):
		ext[i] = (lcm(m, c), p ^ 1)
	ext[-1] = (c, 0)
	seq.extend(ext)
divs = []
for c in C:
	combine(divs, c)
for d in range(D):
	(L, R) = map(int, input().split())
	items = 0
	for (m, p) in divs:
		items += (-1) ** p * (R // m - (L - 1) // m)
	print(items)


from itertools import combinations
from fractions import gcd
N = int(input())
ar = []
for i in range(N):
	ar.append(int(input()))
combs0 = []
combs = []
for i in range(1, N + 1):
	combs0 += combinations(ar, i)
for c in combs0:
	g = 1
	for item in c:
		g = g * item // gcd(g, item)
	combs.append((c, g))

def calc(L, R, num):
	return R // num - (L - 1) // num
for _ in range(int(input())):
	(L, R) = list(map(int, input().split()))
	res = 0
	for c in combs:
		if len(c[0]) & 1:
			res += calc(L, R, c[1])
		else:
			res -= calc(L, R, c[1])
	print(res)


from math import gcd

def lcm(a, b):
	return a * b // gcd(a, b)
n = int(input())
coin = [int(input()) for i in range(n)]
subs = [[0, 0] for i in range(1 << n)]
for i in range(n):
	subs[1 << i] = [coin[i], 1]
for i in range(1, n + 1):
	for j in range(1, 1 << n):
		if subs[j][1] == i:
			for k in range(n):
				if j & 1 << k == 0:
					subs[j | 1 << k] = [lcm(subs[j][0], coin[k]), i + 1]
subs.sort()
rv = []
curr = subs[1][0]
count = 2 * (subs[1][1] % 2) - 1
for i in range(2, len(subs)):
	if subs[i][0] == curr:
		count += 2 * (subs[i][1] % 2) - 1
	else:
		if count != 0:
			rv.append(curr)
			rv.append(count)
		curr = subs[i][0]
		count = 2 * (subs[i][1] % 2) - 1
rv.append(curr)
rv.append(count)
T = int(input())
for run in range(T):
	(a, b) = [int(i) for i in input().split()]
	c = 0
	for i in range(0, len(rv), 2):
		val = (b - a + 1) // rv[i]
		if (b - a + 1) % rv[i] > 0 and (a % rv[i] == 0 or a % rv[i] > (a - 1 + (b - a + 1) % rv[i]) % rv[i]):
			val += 1
		c += rv[i + 1] * val
	print(c)


from fractions import gcd
from itertools import combinations
from math import floor, ceil

def lcm(numbers):
	answer = 1
	for number in numbers:
		answer = answer * number // gcd(answer, number)
	return answer
coins_count = int(input())
unfiltered_coins = []
for i in range(coins_count):
	unfiltered_coins.append(int(input()))
unfiltered_coins.sort()
coins = []
for new_coin in unfiltered_coins:
	if not any([new_coin % coin == 0 for coin in coins]):
		coins.append(new_coin)
precomputed_combinations = [[] for r in range(len(coins) + 1)]
for r in range(1, len(coins) + 1):
	for combo in combinations(coins, r):
		this_lcm = lcm(combo)
		precomputed_combinations[r].append(this_lcm)
day_count = int(input())
for i in range(day_count):
	price_range = [int(part) for part in input().split(' ')]
	price_min = price_range[0]
	price_max = price_range[1]
	total_purchases = 0
	for r in range(len(precomputed_combinations)):
		combinations_for_this_r = precomputed_combinations[r]
		for this_lcm in combinations_for_this_r:
			modulo = price_min % this_lcm
			lowest_hit = price_min + (this_lcm - modulo) if modulo != 0 else price_min
			highest_hit = price_max - price_max % this_lcm
			price_span = highest_hit - lowest_hit
			if r % 2 == 1:
				total_purchases += price_span // this_lcm + 1
			else:
				total_purchases += -(price_span // this_lcm + 1)
	print(total_purchases)


def gcd(a, b):
	while b > 0:
		(a, b) = (b, a % b)
	return a

def lcm(a, b):
	return a * b // gcd(a, b)

def lcmSubset(mask, vals):
	ans = 1
	for i in range(len(vals)):
		if mask & 1 << i:
			ans = lcm(ans, vals[i])
	return ans

def getCoins():
	n = int(input())
	vals = []
	for i in range(n):
		vals.append(int(input()))
	return vals

def makeLcms(vals):
	lcms = []
	for i in range(1 << len(vals)):
		lcms.append(lcmSubset(i, vals))
	return lcms

def getSigns(n):
	pars = []
	for i in range(1 << n):
		a = -1
		for x in range(n):
			if i & 1 << x:
				a *= -1
		pars.append(a)
	return pars

def countOptions(N, coins, lcms, signs):
	ans = 0
	for i in range(1, 1 << len(coins)):
		ans += signs[i] * (N // lcms[i])
	return ans
coins = getCoins()
lcms = makeLcms(coins)
signs = getSigns(len(coins))
days = int(input())
for i in range(days):
	ins = input().split(' ')
	L = int(ins[0])
	U = int(ins[1])
	print(countOptions(U, coins, lcms, signs) - countOptions(L - 1, coins, lcms, signs))


import sys
import itertools
from math import gcd

def lcm(x, y):
	lcm = x * y // gcd(x, y)
	return lcm
debug = False
num_coin_types = int(sys.stdin.readline())
coin_types = [int(sys.stdin.readline()) for _ in range(num_coin_types)]
coin_types = sorted(coin_types)
for i in range(len(coin_types) - 1, -1, -1):
	for j in range(i - 1):
		if coin_types[i] % coin_types[j] == 0:
			del coin_types[i]
			break
if debug:
	print(coin_types)

def list_lcm(l):
	r = l[0]
	for e in l:
		r = lcm(r, e)
	return r

def list_prod(l):
	r = 1
	for e in l:
		r *= e
	return r
overlapped_coin_types = []
coin_types_copy = coin_types.copy()
for comb_len in range(2, len(coin_types_copy) + 1, 2):
	overlapped_coin_types.extend([list_lcm(c) for c in itertools.combinations(coin_types_copy, comb_len)])
for comb_len in range(3, len(coin_types_copy) + 1, 2):
	coin_types.extend([list_lcm(c) for c in itertools.combinations(coin_types_copy, comb_len)])
if debug:
	print('coin_types:%s' % coin_types)
	print('overlapped_coin_types:%s' % overlapped_coin_types)
num_days = int(sys.stdin.readline())
price_ranges = []
for i in range(num_days):
	ranges = [int(x) for x in sys.stdin.readline().split()]
	price_ranges.append(ranges)
if False:
	for price_range in price_ranges:
		(low, high) = price_range
		if 1 in coin_types:
			print(high - low + 1)
			continue
		feasible_item_count = 0
		for price in range(low, high + 1):
			for coin_type in coin_types:
				if price % coin_type == 0:
					feasible_item_count += 1
					break
		print(feasible_item_count)
if False:
	for price_range in price_ranges:
		print(price_range)
		(low, high) = price_range
		if 1 in coin_types:
			print(high - low + 1)
			continue
		feasible_item_count = 0
		feasible_price_set = set()
		for coin_type in coin_types:
			if coin_type > high:
				continue
			min_multiplier = int((low - 1) // coin_type) + 1
			max_multiplier = int(high // coin_type)
			feasible_price_set.update([m * coin_type for m in range(min_multiplier, max_multiplier + 1)])
		feasible_item_count += len(feasible_price_set)
		print(feasible_item_count)
if True:
	for price_range in price_ranges:
		(low, high) = price_range
		if 1 in coin_types:
			print(high - low + 1)
			continue
		feasible_item_count = 0
		if debug:
			print('price_range:%s' % price_range)
		for coin_type in coin_types:
			if coin_type > high:
				continue
			cnt1 = (high - high % coin_type) // coin_type
			cnt2 = (low - 1 - (low - 1) % coin_type) // coin_type
			feasible_item_count += cnt1 - cnt2
		for coin_type in overlapped_coin_types:
			if coin_type > high:
				continue
			cnt1 = (high - high % coin_type) // coin_type
			cnt2 = (low - 1 - (low - 1) % coin_type) // coin_type
			feasible_item_count -= cnt1 - cnt2
		print(feasible_item_count)