已知一个正整数n,(3 <= n <= 15),将所有n的乘方幂以及所有n的乘方幂(有限个且互不相等)之和组成一个递增序列。例如,当n为4时,该序列为:
1, 4, 5, 16, 17, 20, 21……
(4^0, 4^1, 4^0+4^1, 4^2, 4^0+4^2, 4^1+4^2, 4^0+4^1+4^2……)
请求出该序列的第K项(10进制)。
输入只有1行,为2个正整数,两数之间用一个空格隔开:
n K
(n, K的含义与上述描述一致, 且3<=n<=15, 10<=K<=1000)。
输出为计算结果,为一个正整数(注意在所有测试数据中,结果均不会超过2.1*10^9)。整数前不要有空格或其他任何符号。
3 100
981
import java.util.Scanner; public class Main { //就是将k转成2进制,比如k=6,n=4,k的2进制为110,然后以n进制输出来。即1*4^2+1*4^1+0*4^0 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); //进制基数 int n = scanner.nextInt(); //第k个数 int k = scanner.nextInt(); //转化为二进制字符串 String s = Integer.toBinaryString(k); int sum=0; for (int i = 0,len=s.length(); i <len; i++) { int bit=s.charAt(i)=='1'?1:0; sum+=bit*Math.pow(n,len-i-1); } System.out.println(sum); } }
//先上代码 利用位运算解决 #include <iostream> #include <algorithm> using namespace std; int main(){ int n,k; cin>>n>>k; int res=0; for(int i=0;i<10;i++){ //因为k小于1000 所以它的位数不会超过10(2*10=1024),所以循环10次就足够了 if((k&1)==1) //k和1与运算 判断个位数上的数字是否为1 res+=pow(n,i); //将每次的计算结果放入res中 K=K>>1; //k右移 用来下次循环 比较下一位上的数字 } cout<<res<<endl;//最终输出的res值就是k转换为n进制后的值 也就是第k项的值 }
#include<bits/stdc++.h> using namespace std; int main(){ int n,k; cin>>n>>k; vector<int> m; int res=0; for(int i=10;i>=0;i--){ //因为k小于1000 所以它的位数不会超过10(2*10=1024),所以循环10次就足够了 if((k&1)==1) //k和1与运算 判断个位数上的数字是否为1 m.push_back((k>>i)&1); //将k转换成2进制 // //cout<<( (k>>i) & 1);//输出二进制 } for(int j=10;j>=0;j--){ res=res+m[j] * pow(n,10-j); } cout<<res<<endl;//最终输出的res值就是k转换为n进制后的值 也就是第k项的值 return 0; }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int c = 0; int i = 0; int[] arr = new int[k]; while(c<k){ int tmp = (int) Math.pow(n,i++); arr[c++] = tmp; int len = c; for(int j=0;j< len-1 ;j++){ if(c>=k){ break; } arr[c++] = tmp + arr[j]; } } Arrays.sort(arr); System.out.println(arr[k-1]); } }
/* 思路:将k变成二进制后,对应位上为1则表明n的次数 例如: n = 4, k = 5 由于 5 的二进制数为 101 那么对应的数 n^0 + n^2 k = 6 --- 110 n^1 + n^2 */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] str = br.readLine().split(" "); int n = Integer.parseInt(str[0]); int k = Integer.parseInt(str[1]); String bin = Integer.toBinaryString(k); int sum = 0; for(int i = bin.length()-1,j = 0;i>=0;i--){ int temp = (bin.charAt(i) == '1')?1:0; sum = sum + temp*(int)Math.pow(n,j++); } System.out.println(sum); } }
var line=readline().split(' ').map(Number); var num=line[0]; var k=line[1]; // 使用一个数组存储,第一个数设置0是为了方便k var arr=[0]; var j=1 for(var i=1;i<=k;i++){ if(i==1){ arr.push(1) }else if(Math.pow(2,j)==i){ // 在第2,4,8,16项的时候进行 arr.push(Math.pow(num,j)); j++; }else{ // 在其他时候,其他项=前面的项逐个+第二种情况 arr.push(arr[i-Math.pow(2,j-1)]+arr[Math.pow(2,j-1)]) } } console.log(arr[arr.length-1])
def getList(n, k): dp = [0] * (k + 1); dp[1] = 1; i = 2 while i <= k: dp[i] = dp[i // 2] * n; i *= 2 if dp[k] != 0: return dp[k] else: i = 3; while i <= k: start, end = 1, i - 1 while i <= k and start < end: if dp[i] == 0: dp[i] = dp[start] + dp[end]; i += 1; start += 1 i += 1 return dp[k] if __name__ == "__main__": num = str(input()).split(" ") n, k = int(num[0]), int(num[1]) print(getList(n, k))
#include <iostream> #include <math.h> using namespace std; typedef unsigned int uint; uint counting(uint k,const uint n) { uint sum = 0; uint temp; if(k > 1000 || k < 10 || n < 3 || n> 15)//去除错误输入 return 0; //求和n^0*temp + n^1*temp +...+ n^9*temp for(int i=0;i < 10; ++i)//k最大可取1023,10次 { temp = k & 0x0001;//取最后一位的值 0 或 1 sum += (uint)pow((double)n,(double)i)*temp; k = k >> 1;//右移一位 } return sum; } int main() { uint n,K,rec; cin >> n >> K; rec = counting(K,n); cout << rec; return 0; }这题挺唬人的
#include <iostream> #include "string.h" #include "vector" #include <math.h> using namespace std; int main() { int n, k; cin >> n>> k; vector<int> m; int nRes=0; for (int i = 0; i <= 10;i++) { m.push_back((k >> i) & 1); // 判断移位以后最低位是1还是0 } for (int i = 0; i <= 10;i++) { nRes += m[i] * pow(n, i); } cout << nRes; system("pause"); return 0; }
import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] temp = br.readLine().split(" "); //k的二进制表达,权重为n int n = Integer.parseInt(temp[0]), k = Integer.parseInt(temp[1]); int ans = 0, val = 1; while(k!=0){ ans += (k&1)*val; k >>= 1; val *= n; } System.out.println(ans); } }