题解 | #尼科彻斯定理#
尼科彻斯定理
https://www.nowcoder.com/practice/dbace3a5b3c4480e86ee3277f3fe1e85
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
rl.on("line", function (line: string) {
const num = Number(line);
const res: number[] = [];
const avg = num * num;
let loopNum = 1;
let loopMax = 0;
let step = 0;
if (num % 2 === 0) {
res.push(avg - 1, avg + 1);
loopMax = (num - 2) / 2;
step = 1;
} else {
res.push(avg);
loopMax = (num - 1) / 2;
}
while (loopNum <= loopMax) {
res.unshift(avg - step - loopNum * 2);
res.push(avg + step + loopNum * 2);
loopNum++;
}
console.log(res.join("+"));
});
n^3 可以看成 n * n^2, 也就是 n 个 n^2 相加
假设 n 为偶数， 那么 n^3 = ...+ (x-3) + (x-1) + (x+1) + (x+3)+...
由于左右对称， 加减数可以相互约掉， 必须 x - 3 + x + 3 就约掉了 3就变成了 ...+ x + x + x + x + ...
所以 x 就是 n^2, 那么带入
n^3 = n * n^2 = ...+ (n^2 - 3) + (n^2 - 3) + (n^2 + 1) + (n^2 + 3) + ...
所以循环 n/2 次即可查出所有值， 时间复杂度为 O(n)
假设 n 为奇数， 那么 n^3 = ... + (x-2) + x + (x+2) + ...
由于左右对称， 加减数可以相互约掉， 必须 x - 3 + x + 3 就约掉了 3就变成了 ...+ x + x + x + ...
所以 x 也是 n^2, 那么带入
n^3 = n * n^2 = ...+ (n^2 - 2) + (n^2 ) + (n^2 + 2) + ...
所以循环 (n-1)/2 次即可查出所有值， 时间复杂度为 O(n)
投递腾讯云智研发等公司8个岗位 >
查看21道真题和解析
米哈游公司福利 3761人发布