Coders Packet

Problem on Number Theory in C++

By Ebtesam Ahmad Karimi

In this project, I will show you how to solve a problem based on number theory in C++.

Problem Statement:

A function f(n) = (n mod 1) + (n mod 2) + (n mod 3) + ... + (n mod n), where n mod x donates the remainder when dividing n by x. You will be given two numbers L and R, and you have 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.

Constraints:

1 ≤ L ≤ R ≤ 1018

Output

Print the demanded sum in one line.

Example

Input:

5 10

Output:

8

Following is the source code in C++ programming language for above problem statement:
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  ll L,R;
  cin>>L>>R;
  ll l,r;
  ll i=0;
  while(true){
    if(pow(2,i)>=L){
      l=i;
      break;
    }
    i++;
  }
  while(true){
    if(pow(2,i)>R){
      r=i-1;
      break;
    }
    i++;
  }
  ll sum=0;
  while(l<=r){
    sum+=(ll)pow(2,l);
    l++;
  }
  cout<<sum;
}

 

Download project

Reviews Report

Submitted by Ebtesam Ahmad Karimi (ebtesam)

Download packets of source code on Coders Packet