题目链接：点击打开链接
题目大意：
一个区间的价值【L,R】表示区间内所有元素的价值和。
问你一共有多少个区间的价值，是K的非负整数次幂（0,1,2,3,4,5............）。
题解：计算前缀和，并将已计算的前缀和放入map中储存，对于每个新的前缀和，只需去map中查找是否有满足条件的前缀和即可。
Code:
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <map> #define ll long long using namespace std; const int maxn = 1e5 + 10; const ll INF = 1e14 + 20; int n,k; ll a[maxn],ans = 0; ll nums[51],ncnt; map<ll,int> map1; int main() { scanf("%d%d",&n,&k); for(int i = 1;i <= n;i++) scanf("%I64d",&a[i]); if(k == 1) {ncnt = 1;nums[1] = 1;} else if(k == -1) {ncnt = 2;nums[1] = -1;nums[2] = 1;} else { ll temp = 1; for(ncnt = 1;temp <= INF;ncnt++){ nums[ncnt] = temp; temp *= k; }ncnt--; } ll sum = 0;ans = 0; map1[0] = 1; for(int i = 1;i <= n;i++){ sum += a[i]; for(int j = 1;j <= ncnt;j++){ if(map1.count(sum - nums[j])) ans += map1[sum - nums[j]]; } map1[sum]++; } printf("%I64d\n",ans); return 0; }