逆模在矩陣轉置算法

Question

的算法我有一個函數

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

其中M和N是常數（它是矩陣轉置）。不過，我需要爲x解決它。我已經閱讀了關於擴展歐幾里德算法或逆模的歐拉定理的多個主題，但即使我終於找到實現它的方式，一切都表明複雜性會比這更高。任何建議如何進行，請？

Answer 1

的函數可簡化爲

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 %.