1
的算法我有一个函数逆模在矩阵转置算法
y = ((N * x)/(M * N)) + ((N * x) % (M * N))
其中M和N是常数(它是矩阵转置)。不过,我需要为x解决它。我已经阅读了关于扩展欧几里德算法或逆模的欧拉定理的多个主题,但即使我终于找到实现它的方式,一切都表明复杂性会比这更高。任何建议如何进行,请?
的算法我有一个函数逆模在矩阵转置算法
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 %.
非常感谢!我希望我能至少升上20次!我花了几个小时,现在它完美地工作。祝你今天愉快 :) – delmadord