Remainder Quotient – Find all combinations between n & m

Andrew and James are best friends and are fond of puzzles. Andrew challenged James to solve a mathematical problem and promised him to pay $100 if he gives the correct answer.

The problem is that James will be given T pairs of (n,m). Now, all the combinations of all the numbers between n and m(including limits) are taken two at a time.

The left digit in the combination is divided by the right digit in the combination. If the quotient is greater than 1 then the quotient is taken into further consideration.

Frequency of the quotients (greater than 1) is counted and the frequencies greater than1 are added giving the final answer.

*Write a code for James to help him make the calculation and win $100.*

**Explanation**

For T number of test cases you are given two numbers n,m .

Find the total number of pairs(a,b) having integral part of quotient greater than 1,where quotient=a/b.

**CONSTRAINTS:**

1<=T<=10^5

1<=n<=m<=10^5

**Sample Input:**

2

2 6

2 15

**Sample Output:**

3

42

**Detailed Explanation**

2 is the number of test cases.

2,6 and 2,15 are the two test cases.

consider the first test case 2,6

All the numbers between 2 & 6 are considered (including 2 and 6) and pairs are formed:

(2,3) (2,4) (2,5) (2,6)

(3,2) (3,4) (3,5) (3,6)

(4,2) (4,3) (4,5) (4,6)

(5,2) (5,3) (5,4) (5,6)

(6,2) (6,3) (6,4) (6,5)

All the left digits in pair are divided by the right digit in the pair.

0 0 0 0

1 0 0 0

2 1 0 0

2 1 1 0

3 2 1 1

*Quotients greater than 1 are considered.*

2, 2, 3, 2

Frequency of (2) = 3

Frequency of (3) = 1

Since, *we have to consider the frequencies > 1*

Hence, we will ignore Frequency of (3) i.e. = 1

And sum all the other Frequencies that are > 1

The Frequencies > 1 are 3 (i.e Frequency of 2)

Therefore, *answer is 3 for the first test case.*

Time Limit:3.0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 KB

**SOURCE CODE IN PYTHON : :**

import math for i in range(input()): n,m=map(int,raw_input().split()) if m/2 <= n: print 0 continue k=m/2-n j=int(math.ceil(m/2.0))-n a=(k+1)*(j+1) if m%2==0 or (m-n)%2==0: a-=1 print a

**OUTPUT : :**

>

>> ================= RESTART: C:\Users\Second.py ================= 3 2 15 42 2 7 6 2 5000 6245000 >>>

**SOURCE CODE IN C++ : :**

#include<iostream> #include<cstring> using namespace std; int main() { long long int i,n,m,t,p,count,sum,e,s,d; cin>>t; for(i=0;i<t;i++) { sum=0; e=0; cin>>n>>m; p=(m-n)*(m-n+1); long long int arr[p/2]; s=n+1; d=n; while(s<=m) { if(s==d) { s++; d=n; } else if(s/d==1) { d++; } else { arr[e]=s/d; e++; d++; } } int freq[e]; std::memset(freq,-1,e*sizeof(int)); for(int x=0; x<e; x++) { count = 1; for(int y=x+1; y<e; y++) { if((arr[x]>1)&&(arr[x]==arr[y])) { count++; freq[y] = 0; } } if(freq[x]!=0) { freq[x] = count; } if(freq[x]>1) { sum=sum+freq[x]; } } cout<<sum<<endl; } return 0; }

**OUTPUT : :**

3 2 6 3 2 20 80 2 100 2400 Process returned 0