how to find n such that n % x == 0 and (n + 1) % y == 0 ?

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

1 | tourist | 3817 |

2 | jiangly | 3628 |

3 | Benq | 3584 |

4 | slime | 3498 |

5 | maroonrk | 3486 |

5 | djq_cpp | 3486 |

7 | Radewoosh | 3438 |

8 | cnnfls_csy | 3427 |

9 | zh0ukangyang | 3423 |

10 | orzdevinwang | 3399 |

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

1 | -is-this-fft- | 183 |

2 | awoo | 178 |

3 | dario2994 | 168 |

4 | SecondThread | 167 |

5 | Um_nik | 165 |

6 | maroonrk | 164 |

7 | adamant | 163 |

8 | kostka | 162 |

9 | antontrygubO_o | 157 |

10 | errorgorn | 156 |

how to find n such that n % x == 0 and (n + 1) % y == 0 ?

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/05/2022 15:19:57 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

n % x = 0 => n = xk => n+1 = xk + 1 => xk (mod y) = y-1

=> (x%y)*(k%y)%y = y-1 => if any k exists we have one in range [0, y) (if x % y = 0 we don't have any k)

naive approach check for all k [0, y), O(y)

the better approach is if y is the prime number k = (x / power(y-1, y-2)), O(lgy)

There is no need to limit the better approach to the case when k is prime — a generalization is possible for any k.

Let k = n/x. Because n%x == 0, k is an integer. We have (as you said) that n = xk => n+1 = xk+1 => xk+1 $$$\equiv$$$ 0 (mod y) => xk $$$\equiv$$$ -1 (mod y) => x * (-k) $$$\equiv$$$ 1 (mod y).

If x and y are not coprime ( which can be found with euclid's algorithm in O(log(min(x, y))) ), there is no integer "i" that satisfies x * i $$$\equiv$$$ 1 (mod y). So, there is no possible n.

If, however, x and y are coprime, we can apply various theorems to quickly get to a result.

Let "z" be x's modular inverse with respect to y (i.e. the unique number which satisfies 0 <= z < y and x * z $$$\equiv$$$ 1 (mod y)). "z" can be calculated in O(log(min(x, y))) with the extended euclidean algorithm or with a higher complexity using Euler's theorem: $$$x^{\phi (y)} \ \equiv \ 1 \ (mod \ y)$$$.

Now, we have that x * z $$$\equiv$$$ 1 (mod y) => x * (-(-z)) $$$\equiv$$$ 1 (mod y) => x * (-z) $$$\equiv$$$ -1 (mod y) => x * (-z) + 1 $$$\equiv$$$ 0 (mod y) => (x * (-z) + 1) % y == 0.

Summary: in the case of x and y coprime, we have that (x * (-z)) % x == 0 and (x * (-z) + 1) % y == 0. Therefore, "x * (-z)" is a possible and valid choice of n. If, by any chance, it's negative and you don't like it, you can always increase it by a multiple of lcm(x, y). If, by any chance, it's too large, you can decrease it by a multiple of lcm(x, y).

Total time complexity: O(log(min(x, y)))

Yes you are right

so in short

xk (mod y) = y-1

x = ((y-1) * pow(x, phi(y))) % y

so either y is prime -> phi(y) = y-2,

or there is some phi value for y

right?

read up on CRT