report VI VI EN
Register | Login
  • HOME
  • PROBLEMSET
  • ROADMAP
  • COMPETITION
  • TOPIC
  • RANKING
  • GUIDE
  • MASHUP
  • ABOUT
  • CONTACT
  • Problem
  • Submit
  • Results
GCD and LCM - MarisaOJ: Marisa Online Judge

GCD and LCM

Time limit: 1000 ms
Memory limit: 256 MB
Given two positive integers $u, v$, count the number of pairs of positive integers $x, y$ such that their greatest common divisor is $u$ and their least common multiple is $v$. ### Input - A single line containing two positive integers $u, v$. ### Output - Print the number of pairs satisfying the conditions. ### Constraints - $1 \le u, v \le 10^6$. ### Example Input: ``` 3 60 ``` Output: ``` 4 ``` There are $4$ pairs satisfying the conditions: - $(3, 60)$. - $(12, 15)$. - $(15, 12)$. - $(60, 3)$.
Basic number theory
Prime number 2
Sieve of Eratosthenes
Segmented sieve
Prime factors
Maximum GCD
Divisors counting
Largest common divisor
Nearest Element
Divisors counting 2
GCD and LCM
GGCD
Square root sum
Square number
Sum sum sum
Topic
Math
Rating 1200
Solution (1) Solution