Problem Link: https://uva.onlinejudge.org/external/125/12546.pdf

Solution Link: https://ideone.com/q2SX1x

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

1 | Um_nik | 3370 |

2 | Petr | 3325 |

3 | Syloviaely | 3258 |

4 | tourist | 3206 |

5 | Radewoosh | 3158 |

6 | OO0OOO00O0OOO0O0…O | 3102 |

7 | fateice | 3099 |

8 | mnbvmar | 3096 |

9 | HYPERHYPERHYPERC…R | 3071 |

10 | dotorya | 3068 |

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

1 | tourist | 183 |

2 | rng_58 | 169 |

3 | csacademy | 162 |

4 | Petr | 158 |

5 | lewin | 152 |

6 | Swistakk | 151 |

7 | matthew99 | 146 |

8 | Errichto | 142 |

9 | BledDest | 141 |

9 | Zlobober | 141 |

Problem Link: https://uva.onlinejudge.org/external/125/12546.pdf

Solution Link: https://ideone.com/q2SX1x

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/25/2018 07:56:12 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|

Finally I solved it . From seeing your code I can guess that you are constructing all pairs of integers whose LCM is

n. But the problem is that there are an exponential number of possibilities .My approach was the following , first notice that

pandqare always the divisors ofnalso you can create equivalence classes forp. Ifn=p_{1}^{pow1}* ...p_{k}^{powk}is the prime factorisation ofn, then we partition all the divisors into equivalence classes such that a particular equivalence class contains a subset of prime divisors to their highest power and other prime divisors can have smaller powers . For each of the equivalence class inpwe consider how many numbersqcan be created such thatlcm(p,q) =n.This is the abstract of my approach , Take a look at my CODE