Zeldain Garden
Time limit2sMemory limit512 MB
Sum the number of divisors of every integer from N to M, where N and M can reach 10^12.
- Level
Hard8 of 10
- Topics
- Math, Number theory, Brute force, Binary search
- Solved
- No attempts yet
Problem
Boris is the chief executive officer of Rock Anywhere Transport (RAT), a company that specializes in supporting the music industry. In particular, RAT provides discount transport for many popular rock bands. This time Boris has to move a large collection of quality Mexican concert loudspeakers from the port on the North Sea to the far inland capital. The collection is expected to be big, so Boris has to organize a number of lorries to ensure smooth transport. The multitude of lorries carrying the cargo through the country is called a convoy.
Boris wants to transport the whole collection in one go with a single convoy, leaving not a single loudspeaker behind. Strict E.U. regulations demand that for large transports of audio technology, all lorries in the convoy must carry exactly the same number of pieces of equipment.
To meet all the regulations, Boris wants to plan in advance, even though he does not yet know the exact number of loudspeakers, which strongly affects the choice of the number and size of the lorries in the convoy. To examine various scenarios, Boris computes the so-called "variability" for each possible collection size. The variability is the number of different convoys that can be created for that collection size without violating the regulations. Two convoys are different if they consist of a different number of lorries.
For instance, the variability of a collection of 6 loudspeakers is 4, because they can be divided evenly into 1, 2, 3, or 6 lorries.
Input
The input consists of one line with two integers N, M (1 ≤ N ≤ M ≤ 10^12), the minimum and the maximum number of loudspeakers in the collection.
Output
Print a single integer: the sum of the variabilities of all possible collection sizes from N to M, inclusive.