Given an empty array A of infinite length and a positive integer K you have to process 
Q queries of type:    
- ! l r x: Fill the value x in all the empty places in the array from index l to r  (both inclusive).
- ? l r: Print the number of prime factors of K which is also a prime factor of at least one number in A[l], A[l + 1], A[l + 2], … A[r].   

-----Input-----
- The first line contains two space separated integers K and Q respectively.
- Then Q lines follow:
- Each of the $i^{th}$ line contains one of the above two types of queries.

-----Output-----
For each query of the second type, print in a new line the answer to that query. i.e. number of prime factors of K which is also a prime factor of at least one number in A[l], A[l + 1], A[l + 2], … A[r].   

-----Constraints-----
- $1 \leq K, x \leq 10^9$
- $ 1 \leq l \leq r \leq 10^5$
- $ 1 \leq Q \leq 10^5$ 

-----Sample Input-----
20 5

? 1 5

! 3 5 4

? 1 5

! 1 4 15

? 1 5   

-----Sample Output-----
0

1

2   

-----EXPLANATION-----
Initially, all the places in the array are empty. i.e _ _ _ _ _

After first update the array looks like: _ _ 4 4 4

In the range [1, 5] the only factor of 20 which is also a prime factor of at least one number in _ _ 4 4 4  is 2.

After the second update the array looks like: 15 15 4 4 4

In the range [1, 5] the prime factors of 20 i.e. 5 is a prime factor of 15, 15 and 2 is the prime factor of 4, 4, 4.

Source: codechef | Difficulty: VERY_HARD
Tags: Range queries

Segment trees revisited

Number theory

Mathematics

Data structures


Solutions:
import math

def distinctPrimeFactors(num):
	primes = set()
	if num == 2:
		primes.add(num)
	sqrt = int(math.sqrt(num))
	for j in range(2, sqrt + 1):
		if num % j == 0:
			primes.add(j)
			while num % j == 0:
				num //= j
	if num > 2:
		primes.add(num)
	return primes
lst = {}
primes = {}
rangeData = {}
(k, q) = map(int, input().split())
primes[k] = distinctPrimeFactors(k)
for tc in range(q):
	query = input()
	if query[0] == '!':
		(cmd, l, r, x) = query.split()
		l = int(l)
		r = int(r)
		x = int(x)
		start = l
		end = r
		startflag = False
		for i in sorted(rangeData):
			rangeVal = i
			if start > rangeVal[1]:
				continue
			if end < rangeVal[0]:
				break
			startRange = start
			endRange = end
			if start >= rangeVal[0] and start <= rangeVal[1]:
				start = rangeVal[1] + 1
				continue
			if end >= rangeVal[0]:
				endRange = rangeVal[0] - 1
			if startRange <= endRange:
				rangeData[startRange, endRange] = x
				start = max(endRange + 1, rangeVal[1] + 1)
		if start <= end:
			rangeData[start, end] = x
	elif query[0] == '?':
		(cmd, l, r) = query.split()
		l = int(l)
		r = int(r)
		count = 0
		for primenum in primes[k]:
			for currRange in rangeData:
				if not (r < currRange[0] or l > currRange[1]):
					num = rangeData[currRange]
					if num % primenum == 0:
						count += 1
						break
		print(count)


from collections import defaultdict
from math import sqrt

def primefact(n):
	pf = []
	if n % 2 == 0:
		pf.append(2)
		while n % 2 == 0:
			n //= 2
	for i in range(3, int(sqrt(n)) + 1):
		if n % i == 0:
			while n % i == 0:
				n //= i
			pf.append(i)
	if n > 2:
		pf.append(int(n))
	return pf
(K, Q) = map(int, input().split())
prime_range = {}
pfk = primefact(K)
for i in range(Q):
	query = input().split()
	if query[0] == '!':
		l = int(query[1])
		r = int(query[2])
		start = l
		end = r
		for i in sorted(prime_range):
			if start > i[1]:
				continue
			if end < i[0]:
				break
			startrange = start
			endrange = end
			if start >= i[0] and start <= i[1]:
				start = i[1] + 1
				continue
			if end >= i[0]:
				endrange = i[0] - 1
			if startrange <= endrange:
				prime_range[startrange, endrange] = int(query[3])
				start = max(endrange + 1, i[1] + 1)
		if start <= end:
			prime_range[start, end] = int(query[3])
	else:
		l = int(query[1])
		r = int(query[2])
		res = []
		count = 0
		for primenum in pfk:
			for currRange in prime_range:
				if not (r < currRange[0] or l > currRange[1]):
					num = prime_range[currRange]
					if num % primenum == 0:
						count += 1
						break
		res.append(count)
		for r in res:
			print(r)


import math

def primeFactors(num):
	primes = set()
	if num == 2:
		primes.add(num)
	for j in range(2, int(math.sqrt(num)) + 1):
		if num % j == 0:
			primes.add(j)
			while num % j == 0:
				num //= j
	if num > 2:
		primes.add(num)
	return primes
(k, q) = map(int, input().split())
primes = primeFactors(k)
temp = {}
c = 0
result = []
while q > 0:
	query = input().split()
	if query[0] == '!':
		(cstart, cend, x) = (int(query[1]), int(query[2]), int(query[3]))
		for existingvalue in sorted(temp):
			(estart, eend) = (existingvalue[0], existingvalue[1])
			if cstart > eend:
				continue
			if cend < estart:
				break
			(startRange, endRange) = (cstart, cend)
			if cstart >= estart and cstart <= eend:
				cstart = eend + 1
				continue
			if cend >= estart:
				endRange = estart - 1
			if startRange <= endRange:
				temp[startRange, endRange] = x
				cstart = max(endRange + 1, eend + 1)
		if cstart <= cend:
			temp[cstart, cend] = x
	elif query[0] == '?':
		(l, r) = (int(query[1]), int(query[2]))
		count = 0
		for primenum in primes:
			for currRange in temp:
				if not (r < currRange[0] or l > currRange[1]):
					if temp[currRange] % primenum == 0:
						count += 1
						break
		c += 1
		result.append(count)
	q = q - 1
for i in range(c):
	print(result[i])