题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
import java.util.Scanner;
class Main{
public static void main(String[] args) {
// 这个题我做的时候 发现比如k = 3 这个时候最大是3^5 那么前面有3 ^0 3^1 3 ^2 3 ^3 3^4 可以c50 就是3^5 单独组成
//然后c51 3^5 和0 -4之间挑一个 c52 0-4之间挑2个 c53 0- 4之间挑3个 c54 0- 4之间挑5个 c55 0-4之间挑1个 正好是组合数
// 也就是多了32个 2 ^(5) 因为前面5个数 同理对于 第一个3^0 2^(0)前面0个 = 1 第二个3 ^ 1 2 ^(1) 前面1个 第三个3 ^2 2^2
// 第四个3 ^3 2^3 第五个3^4 2^4 然后第六个 3^5 2^5 全部加起来是2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 这是 = 2^6 - 1
// 二进制写法0b 111111 又因为每次比如挑1个都是从低位数来的所以 我们从低位开始找地位数是都为1 然后base 不再是2 而是3
// 把这个k= 3映射成2进制数 然后变成base = base * k;
// 其实这里我们复习了组合数 为了这里是3^5 有32种搭配 因为前面5个数自由搭配后和这个3^5搭配 (1 + 1) ^5 = 32 得到答案
// 因为每个数可以选或者不选
Scanner sc = new Scanner(System.in);
int k = sc.nextInt(), n = sc.nextInt();
int base = 1;
int res = 0;
while (n != 0) {
if ((n & 1) != 0) res += base; // 这里不能是^= base因为 比如k = 3的时候base分别是 = 1 base = 3 base= 9
// ^= 的话1^3 = 2 实际上是4
base *= k;
n >>= 1;
}
System.out.print(res);
}
}