count-numbers-7

Given K prime numbers and T queries of form Ai, Bi, for each query print the number of integers between Ai and Bi (both inclusive) that are divisible by atleast one of the K given primes.     

Input
First line: K and T. 
Second line: K primes.
Next T lines, each contain Ai, Bi.    

Output
Print T lines, denoting the answer to each of the T queries.

Constraints
1 ≤ K ≤ 10 
1 ≤ T ≤ 100 
1 ≤ A ≤ B ≤ 10^9 
Each prime ≤ 10^7

SAMPLE INPUT
2 1
2 3
1 10

SAMPLE OUTPUT
7

Explanation

2,3,4,6,8,9,10 are the 7 numbers.

Difficulty: MEDIUM
Tags: Mathematics

Starter code:

Solutions:
from itertools import combinations

k,t=list(map(int,input().split()))
primes=list(map(int,input().split()))
final=[]
for i in range(1,k+1):
	arr=combinations(primes,i)
	for item in arr:
		final.append(item)

for _ in range(t):
	a,b=list(map(int,input().split()))
	count=0

	i=0
	while i<len(final):
		prod=1
		for ir in final[i]:
			prod=prod*ir
		#print 'prod',prod
		if len(final[i])%2==1:
			count=count+((b/prod)-((a-1)/prod))
		else:
			count=count-((b/prod)-((a-1)/prod))
		i=i+1
	print(count)


def precompute(bin_dict):
	for k in range(1,11):
		for i in range(1,2**k):
			binary = bin(i)[2:].zfill(k)
			ones   = binary.count('1')
			bin_dict[k].append((binary,ones))
		
bin_dict=[[] for x in range(11)]
precompute(bin_dict)
K , T = [int(x) for x in input().split()]
K_primes = [int(x) for x in input().split()]
nums=[]
for bin_tuple in bin_dict[K]:
	mult = 1
	for j in range (K):
		if bin_tuple[0][j]=='1':
			mult*=K_primes[j]
	nums.append((mult,bin_tuple[1]))
 
			

for t in range(T):
	A,B = [int(x) for x in input().split()]
	ans =0
	for item in nums:
	
		res = (B//item[0] - A//item[0])
		if A%item[0] ==0:
			res+=1
		if item[1]%2==0:
			ans-=res
		else:
			ans+=res
	print(ans)
	
 
			
	
	


import math
def func1(a,k,A):
	ans=0
	for i in range((1<<k)-1):
		z=i+1
		prod=1;
		for j in range(k):
			if z&(1<<j):
				prod*=A[j]
		if bin(z).count("1")%2==0:
			ans=int(ans-int(int(a)/int(prod)))
		else:
			ans=int(ans+int(int(a)/int(prod)))
	return ans
		

def main():
	k,t=list(map(int,input().split()))
	A=[int(x) for x in input().split()]
	for i in range(t):
		a,b=list(map(int,input().split()))
		a1=func1(a-1,k,A)
		a2=func1(b,k,A)
		print((a2-a1))

if __name__=='__main__':
	main()


k,t=list(map(int,input().split()))
klis=list(map(int,input().split()))

for _ in range(t):
	ans=0
	a,b=list(map(int,input().split()))
	for i in range(1,2**k):
		l,r=a-1,b
		par=0
		for j in range(k):
			if(i&(1<<j)):
				par+=1
				l/=klis[j]
				r/=klis[j]
		if(par&1):
			ans+=(r-l)
		else:
			ans-=(r-l)
	print(ans)
	




def get(n, low, high):
	div_h = high // n
	div_l = max(0, low - 1) // n
	return div_h - div_l

def stupid(primes, low, high):
	ret = 0
	for i in range(low, high + 1):
		is_div = False
		for p in primes:
			if i % p == 0:
				is_div = True
		ret += is_div
	return ret

k, t = list(map(int, input().split()))
primes = list(map(int, input().split()))

for _ in range(t):
	low, high = list(map(int, input().split()))
	answer = 0

	for i in range(1, 1 << k):
		cur = 1
		par = 0
		for j in range(k):
			if (1 << j) & i:
				par = 1 - par
				cur *= primes[j]

		val = (1 if par == 1 else -1) * get(cur, low, high)
		answer += val

	print(answer)
		



#!/usr/bin/env python
# -*- coding: utf-8 -*-

# https://www.hackerearth.com/problem/algorithm/count-numbers-7/

K, T = [int(x) for x in input().split()]
primes = [int(x) for x in input().split()]


def count_of_divisible(x):
	result = 0
	for i in range(0, 1 << K):
		j = i
		product = 1
		k = 0
		count_of_ones = 0
		while j > 0:
			if j & 1:
				product *= primes[k]
				count_of_ones += 1
			k += 1
			j >>= 1
		if count_of_ones & 1:
			result -= x // product
		else:
			result += x // product
	return x - result

for i in range(0, T):
	A, B = [int(x) for x in input().split()]
	print((count_of_divisible(B) - count_of_divisible(A - 1)))