先上代码,解析后续再写,能点个喜欢就更好了(づ ̄3 ̄)づ╭❤~
// 大数(Arr)乘以整数
function multiplyOneArr(parsedNumber, n) {
let carry = 0
for (let i = parsedNumber.length - 1; i >= 0; i--) {
let multiplied = parsedNumber[i] * n + carry
parsedNumber[i] = multiplied % 10
carry = Math.floor(multiplied / 10)
}
if (carry) {
let carryStr = carry + ''
for (let i = carryStr.length - 1; i >= 0; i--) {
parsedNumber.unshift(parseInt(carryStr[i]))
}
// parsedNumber.unshift(carry)
}
return parsedNumber
}
// 获取(end!)被n整除的次数
function getNu(end, n) {
if (!end || !n) {
throw new Error('getNu required 2 arguments!')
}
let nu = 0
if (end < n) return 0
while (end > 1) {
end = Math.floor(end / n)
nu += end
}
return nu
}
// 求n以内的所有质数
function getPrime(n) {
let primes = [2]
for (let i = 3, j; i <= n; i++) {
for (j = 0; j < primes.length; j++) {
if (i % primes[j] === 0) {
break;
}
}
if (j === primes.length) {
primes.push(i)
}
}
return primes
}
// 统计每个质数的个数
function getcount(primes, n, m) {
let countMap = {}
let n_m = n - m
for (let i = 0; i < primes.length; i++) {
// 可优化?
countMap[primes[i]] = getNu(n, primes[i]) - getNu(n_m, primes[i]) - getNu(m, primes[i])
}
return countMap
}
function getPrimeCount(n, m) {
return getcount(getPrime(n), n, m)
}
function multiplyLoop(n, m) {
// 排除错误数据
if (0 > m || 0 > n || m > n) {
return 0
}
if (m === 1) {
return '1'
}
if (m === n) {
return '1'
}
n -= 1
m -= 1
// 对称,简化计算
if (m > n / 2) {
m = n - m
}
let data = getPrimeCount(n, m)
let result = [1]
for (let i in data) {
if (data[i] > 1) {
result = multiplyOneArr(result, Math.pow(parseInt(i), data[i]))
} else if (data[i] === 1) {
result = multiplyOneArr(result, parseInt(i))
}
}
return result.join('')
}
// (行,列)
multiplyLoop(10000, 5000) // 10000行第5000个数最快耗时51ms