Created
April 10, 2014 12:57
-
-
Save shepherdwind/10379373 to your computer and use it in GitHub Desktop.
辗转相除，计算m * x mod n = 1，已知m < n, 并且m与n互质，求x的值。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| function count(m, n){ | |
| if (n < m) return; | |
| var mod = Math.floor( n / m) | |
| var rem = n % m | |
| var number = 1 | |
| var paths = [] | |
| paths.push([mod, rem, number]) | |
| mod += 1 | |
| rem -= m | |
| paths.push([mod, rem, number]) | |
| if (rem == -1) return paths | |
| add(paths) | |
| var closes = findClose(paths) | |
| while(closes.distance !== -1) { | |
| add(paths, closes.route) | |
| closes = findClose(paths) | |
| } | |
| add(paths, closes.route) | |
| return paths | |
| } | |
| function add(paths, route){ | |
| route = route || [0, 0] | |
| var exp1 = paths[route[0]] | |
| var exp2 = paths[route[1]] | |
| var mod = exp1[0] + exp2[0] | |
| var rem = exp1[1] + exp2[1] | |
| var number = exp1[2] + exp2[2] | |
| paths.push([mod, rem, number]) | |
| } | |
| function findClose(paths){ | |
| var minPositive = 0 | |
| var maxNegative = 0 | |
| var ret = [0, 0] | |
| paths.forEach(function(num, i){ | |
| var rem = num[1] | |
| if (rem > 0) { | |
| // 如果最小正数为0，那么初始化minPositive | |
| if (minPositive === 0) { | |
| minPositive = rem | |
| ret[0] = i | |
| } | |
| // 寻找更小的 | |
| if (minPositive > rem) { | |
| minPositive = rem | |
| ret[0] = i | |
| } | |
| } | |
| if (rem < 0) { | |
| // 如果最小正数为0，那么初始化minPositive | |
| if (maxNegative === 0) { | |
| maxNegative = rem | |
| ret[1] = i | |
| } | |
| // 寻找更小的 | |
| if (maxNegative < rem) { | |
| maxNegative = rem | |
| ret[1] = i | |
| } | |
| } | |
| }) | |
| return { route: ret, distance: minPositive + maxNegative } | |
| } | |
| console.log(count(3, 10000)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment