skpro19's blog

Need help in APAC Round B Problem 2 Large and Problem 3 Small and Large
By skpro19, history, 8 years ago, In English

I am unable to solve the Problem B Large and problem C small and large.

Any help would be much appreciated.

Thanks!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem B Large:

We need to make use of the property: i^a % k = (i + k)^a % k

So e.g., 2^5 % 7 = (2 + 7)^5 % 7 = (2 + 2*7)^5 % 7 = (2 + 3*7)^5 % 7 = ... and so on.
So we only need to iterate from 1 till k.
So iterate from 1 to k and find all the modulo the respective numbers give with A and B. Store the count of numbers in an array, where index is the modulo and value is the total numbers who give that modulo. Then finally iterate over the array and for all i find the value of k - i index and these will be the pair count we are looking for. To exclude same numbers as specified in the problem, use a map or something similar which maintains the record of how many same numbers could possibly contribute to the final answer. Subtract them.

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I think you need to use dynamic programming, for problem C.

→ Reply