You are not logged in. Please login at www.codechef.com to post your questions!

×

How to approach this kind of number theory based problems?

Milly and the Magic Numbers

Milly likes to solve problems very much. Today she is solving a problem in which she has N, L and R and she has to find out the total count of Magic Numbers in [L, R] . Magic Numbers are the numbers which are divisible by at least one prime number in [1, N] . Being a beginner in programming, this one seems too hard for her to solve. So, she is asking you for her help, so your task is to solve this problem.

Input

First line of the input will have a integer T(number of test cases). Then each of the next T lines will contain 3 space separated integers: N, L and R.

Output

For each test case, print a single line having the count of Magic Numbers in [L, R].

Constraints

1 ≤ T ≤ 10

2 ≤ N ≤ 50

1 ≤ L ≤ R ≤ 1018

Sample Input

2

5 1 10

10 10 20

Sample Ouput

8

7

asked 05 Dec '16, 15:11

arpit728's gravatar image

1★arpit728
6831765
accept rate: 10%


@arpit728 It can be easily solved, if you know that the number of multiples of any number(say x) occurs upto certain number(say n) is equal to the $floor(n/x)$ (example: number of multiples of 4 upto 42 is $floor(42/4)=10$). In this question we can calculate number of multiples (between L and R) of each prime number less than N one by one. But this will include some numbers multiple time (example: for n=6, L=1 and R=32, 30 will be counted three times as multiple of 2, 3 and 5.), so we need to subtract that multiples of numbers formed by multiplying prime numbers two at a time. In above example, those numbers will be $2*3=6$, $2*5=10$ and $3*5=15$, but this will remove 30 three times so we need to add the count of multiples formed by multiplying primes taken three at a time (i.e., $2*3*5=30$).
So, it can be generalized as:

total count = $\sum$(count of multiples of primes taken one at a time) - $\sum$(count of multiples of product of prime taken two at a time) + .... $\sum$(count of multiples of product of all prime numbers)

Example: N=6,L=1 and R=31; Let, count(x) = number of multiples of prime number x;
So, total = (count(2) + count(3) + count(5)) - ((count($2*3$) + count($3*5$) + count($2*5$)) + ((count($2*3*5$));
Final answer will be number of multiples till R - number of multiples till L, but in this example as L is 1 so we don't need to calculate seperately for L.
count(2) = $floor(31/2)$ = 15 (2,4,6,8,10,12,14,16,18,20,22,24,26,28,30)
count(3) = $floor(31/3)$ = 10 (3,6,9,12,15,18,21,24,27,30)
count(5) = $floor(31/5)$ = 6 (5,10,15,20,25,30)
count($2*3$) = $floor(31/6)$ = 5 (6,12,18,24,30)
count($3*5$) = $floor(31/15)$ = 2 (15,30)
count($2*5$) = $floor(31/10)$ = 3 (10,20,30)
count($2*3*5$) = $floor(31/30)$ = 1 (30)
total = (15+10+6) - (5+2+3) + (1) = 22

link

answered 05 Dec '16, 15:54

srd091's gravatar image

5★srd091
1.6k111
accept rate: 42%

edited 06 Dec '16, 10:54

@srd091

Please explain the subtraction logic in more details. How the elements that are being counted multiple times is taken care of.

(05 Dec '16, 22:34) arpit7281★

@arpit728 I've added an example to clear the logic.

(06 Dec '16, 00:44) srd0915★

@arpit728 If you feel your question has been answered, mark it as accepted.

(06 Dec '16, 00:46) srd0915★

You can apply a sieve solution...
1. iterate from 2 to n
&nbsp 1. now mark all its multiples
&nbsp 2. add this marked element into a set
2. In the set now find all the marked elements between l and r

Complexity:- O(nlog(n)) for marking the multiples and O(n) for counting...

link

answered 05 Dec '16, 17:54

tejaram15's gravatar image

2★tejaram15
212
accept rate: 0%

edited 05 Dec '16, 17:57

-2

Hey guys, check my website: http://codingeek.org/

link

answered 06 Dec '16, 02:56

ddacot's gravatar image

0★ddacot
-1
accept rate: 0%

-2

Where do you get the 31/2 uhh, mate?

link

answered 06 Dec '16, 10:46

banghasan's gravatar image

0★banghasan
32
accept rate: 8%

@banghasan I've taken the value of R as 31 in the example.

(06 Dec '16, 10:55) srd0915★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,657
×631
×301
×199
×48

question asked: 05 Dec '16, 15:11

question was seen: 1,228 times

last updated: 06 Dec '16, 10:55