OPMODULO - "Operation - Modulo"


Mahmud solved some easy math problems from SPOJ and called himself king of number theory. GodFather GodMATHer Rashad heard it and got angry, so he kidnapped Mahmud. Rashad gave him a task called "Operation - Modulo". Mahmud must solve this task, you know what will happen otherwise ;(. In the Operation - Modulo, we define a function f(n) = (n mod 1) + (n mod 2) + (n mod 3) + ... + (n mod n), where n mod x denotes the remainder when dividing n by x. Rashad interests with integers n such that f(n) = f(n - 1), so he gave Mahmud two numbers L and R, and demands him to find the sum of all integers n such that L ≤ n ≤ R and f(n) = f(n - 1).

Input

First and the only line of input contains two positive integers, L and R (1 ≤ L ≤ R ≤ 1018).

Output

Print the demanded sum in one line.

Example

Input:
1 3

Output:
3

Note: I hope you proved your solution before submitting it :)


hide comments
rajneesh_osho: 2021-08-16 17:56:41

can some one explain it for l=1 and R = 5

aasim3101: 2021-06-18 08:35:26

@mahita_k for the given TC the numbers which are satisfying the condition are 1 and 2 so their sum is 3 which is the answer

mahita_k: 2021-06-17 21:33:40

Help me Please
I aint getting the solution and unable to understand the test case given

[NG]: Solve some easier problems first.

Last edit: 2021-06-18 10:42:18
utkarshag_20: 2021-04-04 19:55:11

nice problem.

Last edit: 2021-04-04 19:57:18
sachin_0001: 2021-02-02 10:52:12

I solved it in 0(n^2) ,and got TLE ,please help me in finding optimal approach

hodobox: 2019-05-26 03:19:35

@drdrunkenstein, so you see that f(1)=f(0) and f(2)=f(1), so both n=1 and n=2 satisfy f(n)=f(n-1), and the answer is the sum of all such numbers, in this case 1+2 = 3.

drdrunkenstein: 2019-04-24 16:58:39

Can someone explain me the test cases?
f(0)=0
f(1)=1%1=0
f(2)=2%1 + 2%2=0
f(3)=3%1 + 3%2 + 3%3=1

So in range 1 to 3 there are only two values of n for which f(n)=f(n-1) i.e. n=1 & n=2.
So how does the test case has answer 3?

sandeep48: 2018-12-25 15:01:15

try to figure out the sequence of no.
nice problem ,+1

kushagrasri: 2018-11-13 08:04:20

once you get the idea, the problem is super easy.
plus, everything fits in long long int. a very interesting problem.
ac in one go!

abhishak69: 2018-10-06 13:59:40

can you give more testcase


Added by:Barish
Date:2018-03-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Deep places of my brain