Count Coprime Pairs with Bounded Product

Code Master

hardSave

MathNumber Theory

Given two positive integers N and L, count the number of pairs of integers (a, b) such that:

1 <= a <= b <= N
gcd(a, b) = 1 (the two numbers are coprime)
a * b <= L (their product does not exceed L)

Return the total count of such pairs as a string.

Example 1

Input

[
  "1",
  "1"
]

Output

Explanation. The only valid pair is (1,1).

Example 2

Input

[
  "5",
  "10"
]

Output

Explanation. The valid pairs (a, b) with 1 <= a <= b <= 5, gcd(a, b) = 1, and a * b <= 10 are (1,1), (1,2), (1,3), (1,4), (1,5), (2,3), and (2,5).

Example 3

Input

[
  "4",
  "6"
]

Output

Explanation. The valid pairs are (1,1), (1,2), (1,3), (1,4), and (2,3).

Example 4

Input

[
  "10",
  "20"
]

Output

Explanation. There are 10 valid pairs with a=1 (1 <= b <= 10), 4 pairs with a=2 (b in {3,5,7,9}), 2 pairs with a=3 (b in {4,5}), and 1 pair with a=4 (b=5). Total is 17 pairs.

Example 5

Input

[
  "10",
  "10"
]

Output

Explanation. There are 10 valid pairs with a=1 and 2 pairs with a=2 (b in {3,5}). Total is 12 pairs.

Example 6

Input

[
  "20",
  "50"
]

Output

Explanation. Counting all coprime pairs (a,b) with 1 <= a <= b <= 20 and a * b <= 50 yields 47 pairs.

Follow-up: Can you compute the answer in O(sqrt(L) * log(L)) time and O(sqrt(L)) space using Mobius inversion and a linear sieve?

Constraints:

1 <= N <= 10^9 1 <= L <= 10^12

Views: 4