from ABC195 ABC195F

  • Thoughts.
    • Factorize prime factors and choose prime factors with no overlap
    • There are 72 of them, so 2^72 ways.
    • Inclusion-elimination principle?
    • Considering after-events?
    • If we make a bipartite graph with prime factors and numbers, we can say that what we need to do is to find a bipartite matching
      • It seems that this is not the way to do it, since it is counting up, rather than seeking the largest one.
    • Bit with or without prime factor bitDP?
      • 2^72 is too big.
    • 72 is Special Constraints.
    • Since it is a continuous integer, prime factors greater than 73 cannot appear twice.
    • We only need to think about prime numbers less than or equal to 72.
    • 20 prime numbers less than 72, does this work?
    • Official Explanation “This solution is fast enough.”
  • COLOCON2018C difficult version tw


This page is auto-translated from /nishio/ABC195F💻 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.