Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef has defined a new type of rooted tree - divisor tree. In this tree, every node has a positive integer written on it. It follows some rules:
The root can have any positive integer written on it.
Suppose a node has the integer A written on it, and suppose A has k proper divisors. [Note: Proper divisors of an integer are all its divisors except the integer itself. 1 has no proper divisor] Then this node will have exactly k child nodes, and each of A's proper divisors will be written on exactly one of the child nodes. For example, a node with number 12 written on it would have children with the numbers 1, 2, 3, 4, and 6 written on them.

You can observe that the nodes have 1 written on them, if and only if, they are leaves. 

The score of a path in this tree is defined as the sum of degrees of all of the nodes in the path. The Score of the tree is defined as the maximum score of a path from the root to one of the leaves.

You are given two integers A, B. You want to find the sum of Scores of all the divisor trees which have n written on their root, where A ≤ n ≤ B.

------ Input ------ 

The only line of the input contains two space separated integers A and B respectively.

------ Output ------ 

Output a single integer corresponding to the answer of the problem.

------ Constraints ------ 

$1 ≤  A ≤ B  ≤ 10^{12}$ 
$ B - A  < 10^{5}$

------ Subtasks ------ 

Subtask #1 (10 points):
$1 ≤  A ≤ B  ≤ 50$

Subtask #2 (25 points):
$1 ≤  A ≤ B  ≤ 10^{6}$
$ B - A < 10^{5}$

Subtask #3 (25 points):
$  A = B  $

Subtask #4 (40 points):
$Original constraints.$ 

----- Sample Input 1 ------ 
11 12
----- Sample Output 1 ------ 
14
----- explanation 1 ------ 

----- Sample Input 2 ------ 
932451 935212
----- Sample Output 2 ------ 
101245
----- explanation 2 ------ 

Input 1.

Here we have, A = 11 and B = 12.

The Score of the divisor tree which has 12 written on its root is 12. This because the path 12 -> 6 -> 3 -> 1  (look at the figure below) has sum of the degrees of all nodes in it = 5 + 4 + 2 + 1 = 12. This is the maximum score of a path among all paths from root to the leaves. Hence, the Score of this tree is 12.

Note that in the figure, the nodes are denoted by (value written on it, degree of node), and the leaves are marked green.

You can find that the score of divisor tree which has 11 written on its root is 2. 

Hence, answer will be 12 + 2 = 14.

Source: codechef | Difficulty: HARD
Tags: Number theory

Data structures

Mathematics


Solutions:
MAX = int(1000000.0) + 1
is_prime = [True] * MAX
(a, b) = map(int, input().strip().split())
factor = [list() for _ in range(b - a + 1)]
for i in range(2, MAX):
	if is_prime[i]:
		for j in range(2 * i, MAX, i):
			is_prime[j] = False
		for j in range((a + i - 1) // i * i, b + 1, i):
			factor[j - a].append(i)
(ans, exp) = (0, list())
for i in range(a, b + 1):
	exp.clear()
	k = i
	for x in factor[i - a]:
		c = 0
		while k % x == 0:
			k //= x
			c += 1
		exp.append(c)
	if k > 1:
		exp.append(1)
	while exp:
		(mul, exp) = (1, sorted(exp))
		for x in exp:
			mul *= x + 1
		ans += mul
		exp[-1] -= 1
		if exp[-1] == 0:
			del exp[-1]
print(ans)


prime = []
check = [0] * (10 ** 6 + 2)

def s(num):
	limit = num ** 0.5 + 2
	prime.append(2)
	check[1] = 1
	for z in range(4, num + 1, 2):
		check[z] = 1
	for i in range(3, num + 1, 2):
		if not check[i]:
			prime.append(i)
			if i <= limit:
				temp = i * 2
				for j in range(i * i, num + 1, temp):
					check[j] = 1

def max_idx(num):
	max = 0
	for i in range(len(num)):
		if num[i] > max:
			max = num[i]
			maxi = i
	return maxi

def loop(num):
	temp = 1
	for i in num:
		temp *= i
	return temp
n = [0] * (10 ** 6 + 7)
s(1000000)
inp = [int(i) for i in input().split()]
b = [[] for i in range(inp[0], inp[1] + 1)]
if inp[0] == 1:
	inp[0] += 1
for i in range(inp[0], inp[1] + 1):
	n[i - inp[0]] = i
for i in range(len(prime)):
	p = prime[i]
	if p > inp[1]:
		break
	for j in range(((inp[0] - 1) // p + 1) * p, inp[1] + 1, p):
		temp = n[j - inp[0]]
		count_temp = 0
		while temp % p == 0:
			temp //= p
			count_temp += 1
		b[j - inp[0]].append(count_temp + 1)
		n[j - inp[0]] = temp
count = 0
for i in range(inp[0], inp[1] + 1):
	if n[i - inp[0]] != 1:
		b[i - inp[0]].append(2)
	c = b[i - inp[0]]
	for j in range(sum(c) - len(c)):
		count += loop(c)
		t = max_idx(c)
		c[t] -= 1
print(count)


from math import sqrt, ceil
cache = {(): 0}

def solve(l):
	if l in cache:
		return cache[l]
	l = list(l)
	s = 1
	for x in l:
		s *= x + 1
	l[0] -= 1
	l = list(reversed(sorted(l)))
	if not l[-1]:
		l.pop()
	return s + solve(tuple(l))

def sieve_primes(n):
	table = [True] * (n + 1)
	for x in range(3, ceil(sqrt(n)) + 1, 2):
		if not table[x]:
			continue
		for y in range(x * x, n + 1, 2 * x):
			table[y] = False
	primes = [2]
	for x in range(3, n + 1, 2):
		if table[x]:
			primes.append(x)
	return primes
primes = sieve_primes(1000000)
(a, b) = (int(x) for x in input().split())
c = ceil(sqrt(b))
table = [(x, []) for x in range(a, b + 1)]
for p in primes:
	if p > c:
		break
	for x in range(ceil(a / p) * p, b + 1, p):
		(y, z) = table[x - a]
		d = 0
		while y % p == 0:
			y //= p
			d += 1
		if d:
			z.append(d)
			table[x - a] = (y, z)
s = 0
for (y, z) in table:
	if y > 1:
		z.append(1)
	z = tuple(reversed(sorted(z)))
	s += solve(z)
print(s)


mark = [0] * (10 ** 6 + 2)
prime = []

def reduce(x):
	a = 1
	for i in x:
		a *= i
	return a

def to(a):
	max = 0
	for i in range(len(a)):
		if a[i] > max:
			max = a[i]
			maxIndex = i
	return maxIndex

def sieve(n):
	mark[1] = 1
	tmp = n ** 0.5 + 2
	prime.append(2)
	for i in range(4, n + 1, 2):
		mark[i] = 1
	for i in range(3, n + 1, 2):
		if not mark[i]:
			prime.append(i)
			if i <= tmp:
				tmp1 = i * 2
				for j in range(i * i, n + 1, tmp1):
					mark[j] = 1
num = [0] * (10 ** 6 + 6)
sieve(1000000)
a = [int(j) for j in input().split()]
test = [[] for i in range(a[0], a[1] + 1)]
if a[0] == 1:
	a[0] += 1
for i in range(a[0], a[1] + 1):
	num[i - a[0]] = i
for i in range(len(prime)):
	p = prime[i]
	if p > a[1]:
		break
	for j in range(((a[0] - 1) // p + 1) * p, a[1] + 1, p):
		n = num[j - a[0]]
		cnt = 0
		while n % p == 0:
			n //= p
			cnt += 1
		test[j - a[0]].append(cnt + 1)
		num[j - a[0]] = n
su = 0
for i in range(a[0], a[1] + 1):
	if num[i - a[0]] != 1:
		test[i - a[0]].append(2)
	b = test[i - a[0]]
	for j in range(sum(b) - len(b)):
		su += reduce(b)
		b[to(b)] -= 1
print(su)


from math import *
from collections import defaultdict
(a, b) = map(int, input().split())
ans = 0
a = max(2, a)
try:
	xrange
except NameError:
	xrange = range

def primeListSofE(n):
	maxI = (n - 3) // 2
	maxP = int(sqrt(n))
	sieve = [True for j in xrange(maxI + 1)]
	for p in xrange(3, maxP + 1, 2):
		i = (p - 3) // 2
		if sieve[i]:
			i2 = (p * p - 3) // 2
			for k in xrange(i2, maxI + 1, p):
				sieve[k] = False
	ret = [2] + [2 * j + 3 for j in xrange(len(sieve)) if sieve[j]]
	return ret
mx = int(sqrt(b)) + 1
prime = primeListSofE(mx)
try:
	har = defaultdict(list)
	vij = {i: i for i in xrange(a, b + 1)}
except:
	print(0)
	exit(0)
for i in prime:
	lx = a
	ax = i - a % i
	if a % i != 0:
		lx = a + ax
	for j in xrange(lx, b + 1, i):
		chk = vij[j]
		if chk % i == 0:
			cnt = 0
			tota = vij[j]
			while tota % i == 0:
				cnt += 1
				tota /= i
			vij[j] = tota
			har[j].append(cnt + 1)
for i in har:
	if vij[i] != 1:
		har[i].append(2)
for i in har:
	ab = har[i][:]
	from operator import mul
	mx = 1
	for i in ab:
		mx *= i
	anx = mx
	ab.sort()
	while True:
		drop = ab[-1]
		if drop == 1:
			break
		mx /= drop
		drop -= 1
		mx *= drop
		if mx == 1:
			break
		anx += mx
		ab[-1] = drop
		ab.sort()
	ans += anx
prime = 0
for i in xrange(a, b + 1):
	if i not in har:
		prime += 1
print(int(ans + prime * 2))


import functools
from math import sqrt
from operator import mul
MAX_NUM_FACTORS = 30

def compute_factors(A, B, devisors):
	factors = [None for i in range(A, B + 1)]
	for i in range(0, B - A + 1):
		num_devisors = devisors[i]
		l = len(num_devisors)
		num_factors = []
		candidates = list(num_devisors)
		filtered = []
		while candidates:
			currrent_prime = candidates[0]
			num_factors.append(currrent_prime)
			for k in range(1, len(candidates)):
				if candidates[k] % currrent_prime != 0:
					filtered.append(candidates[k])
			candidates = filtered
			filtered = []
		factors[i] = num_factors
	if A == 1:
		factors[0] = []
	return factors

def compute_devisors(A, B):
	devisors1 = [[] for i in range(A, B + 1)]
	devisors2 = [[] for i in range(A, B + 1)]
	for i in range(2, int(sqrt(B)) + 1):
		r = A % i
		if r == 0:
			n = A
		else:
			n = A - r + i
		j = n
		while j <= B:
			if i * i > j:
				j += i
				continue
			devisors1[j - A].append(i)
			if i * i != j:
				devisors2[j - A].append(j / i)
			j += i
	[devisors1[i].extend(reversed(devisors2[i])) for i in range(0, B - A + 1)]
	[devisors1[i].append(A + i) for i in range(0, B - A + 1)]
	return devisors1

def get_max_power_naive(p, n):
	count = 0
	d = 1
	while True:
		next_d = d * p
		if n % next_d != 0:
			break
		count += 1
		d = next_d
	return (count, d)

def compute_powers(A, B, factors):
	powers = [None for i in range(A, B + 1)]
	for i in range(0, B - A + 1):
		num = A + i
		num_factors = factors[i]
		if num_factors:
			fact_prod = functools.reduce(mul, num_factors)
		else:
			fact_prod = 1
		current_num = num / fact_prod
		num_powers = [-1 for s in range(len(num_factors))]
		for j in range(0, len(num_factors)):
			(power, exp) = get_max_power_naive(num_factors[j], current_num)
			num_powers[j] = power + 1
			current_num /= exp
		powers[i] = num_powers
	return powers
tree_scores = {}

def cts(powers):
	power_prod = functools.reduce(lambda s, v: s * (v + 1), powers, 1) - 1
	m = powers[0]
	last_max_index = 0
	while last_max_index + 1 < len(powers) and powers[last_max_index + 1] == m:
		last_max_index += 1
	pred_power = list(powers)
	pred_power[last_max_index] -= 1
	pred_value = tree_scores[tuple(pred_power)]
	tree_scores[tuple(powers)] = power_prod + pred_value + 1

def precompute_tree_scores(max_num_factors):
	powers = [0 for i in range(max_num_factors)]
	tree_scores[tuple(powers)] = 0
	count = 0
	while True:
		powers[0] += 1
		count += 1
		while count >= max_num_factors + 1:
			if index == max_num_factors - 1:
				return
			index += 1
			powers[index] += 1
			count += 1
			v = powers[index]
			for i in range(index):
				count -= powers[i]
				count += v
				powers[i] = v
		index = 0
		cts(powers)

def compute_sum(A, B, powers):
	S = 0
	for i in range(0, B - A + 1):
		powers[i].sort(reverse=True)
		pad_length = MAX_NUM_FACTORS - len(powers[i])
		powers[i].extend([0 for j in range(pad_length)])
		if sum(powers[i]) == 0:
			if A == 1 and i == 0:
				S += 0
			else:
				S += 2
		else:
			S += tree_scores[tuple(powers[i])]
	return S
data = input().strip().split()
(A, B) = (int(data[0]), int(data[1]))
devisors = compute_devisors(A, B)
factors = compute_factors(A, B, devisors)
powers = compute_powers(A, B, factors)
precompute_tree_scores(MAX_NUM_FACTORS)
print(compute_sum(A, B, powers))


import heapq, math
ispr = [1] * (10 ** 6 + 5)
ispr[0] = ispr[1] = 0
primes = []
for i in range(2, len(ispr)):
	if ispr[i]:
		primes.append(i)
		for j in range(i + i, len(ispr), i):
			ispr[j] = 0

def getdivlist(A, B):
	nums = [i for i in range(A, B + 1)]
	divlistall = [[] for i in range(B - A + 1)]
	for p in primes:
		st = p * math.ceil(A / p)
		for i in range(st, B + 1, p):
			c = 0
			while nums[i - A] % p == 0:
				nums[i - A] //= p
				c += 1
			divlistall[i - A].append(c)
	for i in range(B - A + 1):
		if nums[i] > 1:
			divlistall[i].append(1)
	return divlistall
(A, B) = map(int, input().split())
divlistall = getdivlist(A, B)
total = 0
for divlist in divlistall:
	prod = 1
	for d in divlist:
		prod *= 1 + d
	divlist = [-d for d in divlist]
	count = 0
	heapq.heapify(divlist)
	while divlist:
		count += prod
		largest = -heapq.heappop(divlist)
		prod = prod // (largest + 1) * largest
		largest -= 1
		if largest:
			heapq.heappush(divlist, -largest)
	total += count
print(total)