# Problem Link:

# Difficulty:

Easy

# Pre-requisites:

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 most2 * √Ndistinct 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:

- Mahbub’s

```
(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester1/COOLGUYS.cpp)
2. Sergey's
```

(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester2/COOLGUYS.cpp)

# Editorialist’s Solution:

Can be found here