- 1.题目
- 2.分析
- 方法1:看成二进制
- 方法2:看成前面项的累加和
- 3.代码
- 方法1:看成二进制
- 方法2:看成前面项的累加和
- 4.总结
- 5.更新日志
题目链接
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld
题目描述
给定一个正整数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)。(整数前不要有空格和其他符号)。
示例1
输入
3 100
输出
981
分析题目中的幂次,可以将其转换为二进制对应的幂次和。
//根据题目意思 将每一项的下标转换为 二进制 刚好可以对应
//1 2 3 4 5 6 7
//001 010 011 100 101 110 111
//3^0*1 3^0*0+3^1*1 3^0*1+3^1*1 ..................
方法2:看成前面项的累加和
3.代码
方法1:看成二进制
#include
using namespace std;
typedef long long ll;
int main()
{
ll num=0;
int k,n;
cin>>k>>n;
int c=0; //幂次
while(n>0)
{
if(n&1)
{
num+=pow(k,c);
}
c++; //同时幂次也要上移
n>>=1; //判断n的下一位
}
cout<<num;
return 0;
}
方法2:看成前面项的累加和
#include
using namespace std;
typedef long long ll;
int main()
{
ll a[2000]; //存放每一项的数字(数组开大点)
int i,n,k;
int j=0; //幂次
cin>>k>>n;
for(int i=1;i<=n;j++) //将n项全部表示出来 (幂次要记得更新)
{
a[i++]=pow(k,j);
int temp=i;
for(int s=1;s<temp-1;s++)
{
a[i++]=a[temp-1]+a[s]; //依次与前面的项相加 ,赋给下一项
}
}
cout<<a[n];
return 0;
}
4.总结
要灵活使用2进制解决问题
同时也要注意规律的寻找
2022.5.4 整理上传
欢迎交流、讨论、指正~
不理解、不正确之处欢迎评论留言~
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)