unt311's blog

upto what limit can we represent a fraction using modulo
By unt311, history, 3 years ago, In English

for positive numbers x, y (both less than 1e9)

Can the fraction of (x / y) be represented as x * inv(y) for various values of x and y (within 1e9)

I get a Wrong Answer in a div3 D problem by doing so [submission]

NOTE: I am using 1e9 + 7 for modulo operations in calculating the inverse

  • Vote: I like it
  • +5
  • Vote: I do not like it

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

I fear, you cannot really use this here like this. Let's look at this example:

2 2 5
3 3 4

The answer would be 2, since we can take $$$d=-3/2$$$ and the first two rows will yield $$$0$$$.

Imagine you were using $$$7$$$ as prime number for the modulo operations (just so we don't need to handle big numbers at the moment.). Then your answer would be $$$d=-3/2$$$. The inverse of $$$2$$$ is $$$4$$$ since $$$2\cdot4=1$$$. But now let's have a look at the third value pair. $$$5 \cdot d+4=-5 \cdot 3 \cdot 4+4=-60+4=0$$$ in $$$mod 7$$$. Or in your calculations in your code the $$$d$$$ will be the same for all 3 cases. $$$2\cdot inv(3)=2\cdot5=3=5\cdot 2=5 \cdot inv(4)$$$. So your program will output 3 (using $$$mod 7$$$) although it should be 2.

Now the same happens with your big modulo. You could try out different modulos, then maybe your submission will pass, but still it can be hacked pretty fast.

But all in all, I think this was a clever idea! I guess to pass though you should use a good representation for rational numbers in this task.

→ Reply