如何获得真正的欧几里德余数？

Question

我有两个unsigned long s a和q我想找到一个数字n介于0和q-1之间，使得n + a可以被q整除（没有溢出）。

换句话说，我试图找到一个位于0和q-1之间的（便携式）计算方法(-a)%q。 （该表达式的符号在C89中是实现定义的。）执行此操作的好方法是什么？

Answer 1

你在找什么在数学上等价于（q - a）mod q，而q相当于（q - （a mod q））mod q。我认为你应该能够计算出如下：

unsigned long result = (q - (a % q)) % q;