蓝桥杯算法训练数列

本是古典何须时尚 2022-04-23 12:50 314阅读 0赞

问题描述
    　　给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：
    　　1，3，4，9，10，12，13，…
    　　（该序列实际上就是：30，31，30+31，32，30+32，31+32，30+31+32，…）
    　　请你求出这个序列的第N项的值（用10进制数表示）。
    　　例如，对于k=3，N=100，正确答案应该是981。
    输入格式
    　　只有1行，为2个正整数，用一个空格隔开：
    　　k N
    　　（k、N的含义与上述的问题描述一致，且3≤k≤15，10≤N≤1000）。
    输出格式
    　　计算结果，是一个正整数（在所有的测试数据中，结果均不超过2.1*109）。（整数前不要有空格和其他符号）。
    样例输入
    3 100
    样例输出
    981

import java.util.Scanner;
    
    public class Main{
               /* 当k=3时
    			N=1,即0001表示3^0存在
    			N=2,即0010表示3^1存在
    			N=3,即0011表示3^0和3^1存在
    			N=4,即0100表示3^2存在
    			N=5,即0101表示3^2和3^0存在
    			...
    			思路:把N转为二进制,然后每一位乘上幂即可
    			*/
    public static void main (String args[]){
    	Scanner s=new Scanner(System.in);
    	int[] a=new int[1000];
    	int sum=0;
    	int k=s.nextInt();
    	int n=s.nextInt();
    	int index=1;
        while(n!=0) {//转为二进制存在数组a，从索引1开始
        	a[index++]=n%2;
        	n=n/2;
        }
        int len=index--;//减去1即为二进制的长度
      for(int i=1;i<=len;i++) {
    	 sum+=a[i]*pow(k,i-1);
      }
      System.out.println(sum);
    }
    
    private static int pow(int k, int n) {//求幂
    	// TODO 自动生成的方法存根
    	int sum=1;
    	for(int i=1;i<=n;i++) {
    		sum=sum*k;
    	}
    	return sum;
    }
    }