Tap here to switch tabs
Problem
Submissions

Problem: Nth Magical Number

Nth Magical Number asks you to find the nth positive integer divisible by either of two given numbers, returning the result modulo a large prime.

Statement

Given three integers n, a, and b, return the nth magical number.

A magical number is defined as a positive integer that is divisible by either a or b.

As the result may be very large, return it modulo 109+710^9+7.

Constraints:

  • 1≤1 \leq n ≤109\leq 10^9

  • 2≤2 \leq a, b ≤4×104\leq 4 \times 10^4

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Nth Magical Number

Nth Magical Number asks you to find the nth positive integer divisible by either of two given numbers, returning the result modulo a large prime.

Statement

Given three integers n, a, and b, return the nth magical number.

A magical number is defined as a positive integer that is divisible by either a or b.

As the result may be very large, return it modulo 109+710^9+7.

Constraints:

  • 1≤1 \leq n ≤109\leq 10^9

  • 2≤2 \leq a, b ≤4×104\leq 4 \times 10^4