Tintin's blog

Dima and Two Sequences
By Tintin, 12 years ago, In English

Hi,

Here Problem link:http://codeforces.net/contest/273/problem/B

Here m can be non prime number.How can I handle the division property? I read tutorialhttp://codeforces.net/blog/entry/6625, but I can't understand properly. Can you reply, thanks

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The exact number you want to compute is a fraction, with some factorials in the nominator and 2^(number of pairs that occur in both sequences). So, you can just pre-compute all the required factorials, and split each into a number of form o*(2^p), where o is an odd number modulo M and x >= 0. Then, you can handle separately all the odd prime factors (merged in o) and the power of 2.

→ Reply