Java教程

洛谷 P1062数列题解--zhengjun

本文主要是介绍洛谷 P1062数列题解--zhengjun,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述

给定一个正整数\(k(3≤k≤15)\),把所有\(k\)的方幂及所有有限个互不相等的\(k\)的方幂之和构成一个递增的序列,例如,当\(k=3\)时,这个序列是:

\(1,3,4,9,10,12,13,\cdots\)

(该序列实际上就是:\(3^0,3^1,3^0+3^1,3^2,3^0+3^2,3^1+3^2,3^0+3^1+3^2,…\))

请你求出这个序列的第\(N\)项的值(用\(10\)进制数表示)。

例如,对于\(k=3\),\(N=100\),正确答案应该是\(981\)。

输入格式

\(2\)个正整数,用一个空格隔开:

\(k,N\)(\(k\)、\(N\)的含义与上述的问题描述一致,且\(3≤k≤15,10≤N≤1000\))。

输出格式

\(1\)个正整数。(整数前不要有空格和其他符号)。

输入输出样例

输入 #1 复制
3 100
输出 #1 复制
981

说明/提示

\(NOIP\ 2006\) 普及组 第四题

思路

首先,这一定是一道找规律的题目。

把那一串数写成\(k\)进制的形式就是:

\(001,010,011,100,101,110,111,\cdots\)

乍眼一看,不就是传说中的谔进制吗?

进制转换成十进制:

\(1,2,3,4,5,6,7,\dots\)

清晰明了,让我们求第\(N\)项,就是\(N\)

然后倒推回去成谔进制,再直接当做\(k\)进制,又转换成\(10\)进制,就是答案

最后注意开龙龙\((long\ long)\)

代码

#include<bits/stdc++.h>
using namespace std;
int k,n;
int a[11],len,i;
long long ans,j;
int main(){
	scanf("%d%d",&k,&n);
	for(i=n;i;i/=2)a[++len]=i%2;
	for(i=1,j=1;i<=len;i++,j*=k)ans+=a[i]*j;
	printf("%lld",ans);
	return 0;
}

谢谢--zhengjun

这篇关于洛谷 P1062数列题解--zhengjun的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!