Note: Factors and prime factorization are two different things. The factors of a number are the numbers that are divisible by it. Example: 12: {1, 2, 3, 4, 6, 12}.

# | User | Rating |
---|---|---|

1 | tourist | 3687 |

2 | ecnerwala | 3600 |

3 | Benq | 3503 |

4 | ksun48 | 3421 |

5 | Um_nik | 3412 |

6 | Radewoosh | 3382 |

7 | maroonrk | 3323 |

8 | Itst | 3239 |

9 | apiadu | 3238 |

10 | ko_osaga | 3232 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 204 |

2 | Monogon | 194 |

2 | SecondThread | 194 |

4 | vovuh | 188 |

4 | Ashishgup | 188 |

6 | pikmike | 186 |

6 | Um_nik | 186 |

8 | antontrygubO_o | 185 |

9 | pashka | 170 |

10 | Radewoosh | 167 |

Note: Factors and prime factorization are two different things. The factors of a number are the numbers that are divisible by it. Example: 12: {1, 2, 3, 4, 6, 12}.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/24/2020 17:13:36 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Yes

Sir, thank you bro sir.

To do so, you need to first prime factorize the number. This can be done in $$$O(n)$$$ precomputation time and $$$O(\log n)$$$ per query. You can do so by keeping the smallest prime divisor of each number (for more details see here).

Now that you have the number in its prime factorized form $$${p_1}^{a_1}{p_2}^{a_2}{p_3}^{a_3}\ldots$$$, you can generate factors using a recursive approach. First note that all factors of this number are prime factorized to $$${p_1}^{b_1}{p_2}^{b_2}{p_3}^{b_3}\ldots$$$ where $$$0 \leq b_i \leq a_i$$$. You can recursively generate all sequences of $$$b$$$ that satisfy this requirement and now you have all factors of the number.

Note that this works in $$$O(\log n + k)$$$ time, where $$$k$$$ is the number of factors this number has. Check out highly composite numbers, which is an upper bound to $$$k$$$. I don't know of any ways to solve this problem without the $$$O(n)$$$ precomputation though.

A number can have more than $$$O(\log{n})$$$ divisors ($$$O(\sqrt[3]{n})$$$ is a useful bound in practice, the actual bound is a little more involved, see https://math.stackexchange.com/questions/63687/bound-for-divisor-function ), and an algorithm that finds all divisors is bounded below by the number of divisors, so there is no algorithm for finding divisors in $$$O(\log{n})$$$ time.

A number has $$$O(\log{n})$$$ prime factors, so you might be able to use that.

Thanks for the informative explanation!