Practice

Contest

Easy

Number theory

# Problem:

Given an integer N. Two integers A and B are chosen randomly from [1…N]. Find the probability that gcd(A, B) = B as a reduced fraction.

# Explanation:

Stating that gcd(A, B) = B is same as saying that B is a factor of A. Therefore, our problem is equivalent to finding

number of ordered pairs (A, B) such that B is a factor of A / N * N

The numerator can be written equivalently in two forms as below:

sum [over A=1 to N] number of factors of A

sum [over B=1 to N] number of multiples of B less than N+1

While it is difficult to find the summands of First sum, the second sum can be written down very simply as

sum B=1 N ⌊ N/B ⌋

At this point a very handy fact comes to our rescue.

The sequence ⌊ N/i ⌋ has at most 2 * √N distinct values.

This is because for i > √N, ⌊ N/i ⌋ < √N. Therefore for i = √N + 1 to N, it has only √N distinct values.

The above fact can be used to our advantage. We can sum up the series by summing up, for each distinct value in the sequence, its number of occurrences.

⌊ N/i ⌋ = K
⇒ K ≤ N/i < K+1
⇒ N/(K+1) < i ≤ N/K
⇒ ⌊ N/(K+1) ⌋ < i ≤ ⌊ N/K ⌋

Using the ideas discussed above, here is the psudo code of final solution:

``````
sum = 0
K = N
imin = 1
while imin ≤ N
imax = ⌊ N/K ⌋
sum += K*(imax - imin + 1)
imin = imax + 1
K = N/imin
g = gcd(N * N, sum)
print sum/g, N * N/g

``````

# Setter’s Solution:

Can be found here

# Tester’s Solution:

1. Mahbub’s
``````
2. Sergey's

``````

# Editorialist’s Solution:

Can be found here

9 Likes

Looks like most of the people have used a logic something like this:

int root=sqrt(num);

for(i = 1 to root)
res=res+(num/i);

can somebody explain the logic behind this approach???

3 Likes

Because it’s “well known” sequence - http://oeis.org/A006218

3 Likes

@orchidmajumder Even I used the approach you just mentioned. I seriously don’t know why it works, but OEIS suggests so (look under the PROG section).

I too used the same approach. A detailed explanation is given in this link http://matwbn.icm.edu.pl/ksiazki/mon/mon42/mon4204.pdf . Pages 159 - 163 cover the same!

@scep2 The given link issues a 404

Edit: The above link is working. Strip the period (.) off from the right.

@tijoforyou darn yeah! Dint realise till you pointed it out. Fixed the link i earlier posted. Try this : http://matwbn.icm.edu.pl/ksiazki/mon/mon42/mon4204.pdf

3 Likes

The first sum can be found by the divisor summatory function :

2 Likes

I used exactly the same approach as the editorial explained but still got TLE maybe due to BigInteger

class what do you think?

You do not need biginteger class, because all values are only upto 10^9.

i was thinking cumulated sum or product that will exceed 10^9

you know that this fraction (a/b) is always <= 1, right? And b = n*n, while n <= 10^9, n^2 <= 10^18, so long is ok…

Also converting int to String just to get BigInteger is not a good idea, look at BigInteger.valueOf() function…

from i=1 to 7, sqrt(n)=2
n/i values will be 7,3,2,1,1,1,1 repectively. Then What does it mean…
The sequence ⌊ N/i ⌋ has at most 2 * √N distinct values.
This is because for i > √N, ⌊ N/i ⌋ < √N. Therefore for i = √N + 1 to N, it has only √N distinct values.

sqrt(N) = 2.65…
so, N/i, for i > 2.65…, (i.e. i=3,4,5,6,7 )
takes at most sqrt(N) = 2.65… different values (in our case, these values are 1 and 2 for i = 3 and 4,5,6,7)

So, in english, my argument is:
for i = 1, 2 … sqrt(N) there can be atmost sqrt(N) distinct values.
In our case, this holds for i = 1 and 2, so we have two distinct values here(these value are 7 and 3).

for i>sqrt(N), there can be sqrt(N) distinct values.
In our case, it holds for i = 3,4,5,6,7. So there are only sqrt(N) [=2] distinct values for all these i’s(these values are 2 and 1).

1 Like

great work guys

Thank you. Many people have solved it by iterating i over 1 to sqrt(n) taking sum of (n/i) and then `2*sum-(sqrt(n)*sqrt(n))`. How did we get this equation?

whats wrong in this solution

//