c - 矩阵转置算法的逆模运算

我有个功能

y = ((N * x) / (M * N)) + ((N * x) % (M * N))

其中m和n是常数（用于矩阵换位）。然而，我需要为X来解决它。我已经阅读了关于欧几里德算法或逆模欧拉定理的多个主题，但是即使我最终找到了实现它的方法，一切都表明复杂性比这要高得多。有什么建议吗？

最佳答案

功能简化为

y = (x / M) + N * (x % M).

对于y这样的0 ≤ y < M * N，有一个独特的解决方案

x = (y / N) + M * (y % N),

因为这毕竟是一个转置。证明是经过计算的。

  ((x / M) + N * (x % M)) / N + M *  (((x / M)     +  N * (x % M)) % N)
= ((x / M) + N * (x % M)) / N + M * ((((x / M) % N + (N * (x % M)) % N) % N)
= ((x / M) + N * (x % M)) / N + M *  (((x / M) % N)                     % N)
  since (N * ...) % N = 0
= ((x / M) + N * (x % M)) / N + M *    (x / M)
  since 0 ≤ x / M < N
=                 x % M       + M *    (x / M)
  since 0 ≤ x / M < N and N divides N * (x % M)
= x
  by the Euclidean property of / and %.

关于c - 矩阵转置算法的逆模运算，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33469645/