问题描述
给定一个正整数 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
思路:
30,31,30+31,32,30+32,31+32,30+31+32
分别对应 3 进制的 1, 10, 11, 100,101, 110, 111,
而这些 3 进制数又对应 2 进制数的 1,2,3,4,5,6,7(相当于是下标)
因此, 我们可以逆向来求, 比如要求 p 的第 n 个数, 我们把 n 转换成 2 进制数, 再按位加 pi 即可.
- #include <stdio.h>
- #include <string.h>
- #include <iostream>
- #include <string>
- #include <math.h>
- #include <algorithm>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <set>
- #include <map>
- #include <sstream>
- const int INF=0x3f3f3f3f;
- typedef long long LL;
- const int mod=1e9+7;
- const int maxn=1e4+10;
- using namespace std;
- int main()
- {
- #ifdef DEBUG
- freopen("sample.txt","r",stdin);
- #endif
- int n,p;
- scanf("%d %d",&p,&n);
- int sum=0;
- int temp=1;
- while(n)
- {
- if(n%2) sum+=temp;
- n/=2;
- temp*=p;
- }
- printf("%d\n",sum);
- return 0;
- }
- -
来源: http://www.bubuko.com/infodetail-3412432.html