网站建设验收单意见怎么写,wordpress 主题制作 评论,动画制作软件下载中文版免费版,招工平台网求给定区间 [X,Y] 中满足下列条件的整数个数#xff1a;这个数恰好等于 K个互不相等的 B的整数次幂之和。
例如#xff0c;设 X15,Y20,K2,B2#xff0c;则有且仅有下列三个数满足题意#xff1a; 172420 182421 202422
输入格式
第一行包含两个整数 X和 Y#xff0c;接…求给定区间 [X,Y] 中满足下列条件的整数个数这个数恰好等于 K个互不相等的 B的整数次幂之和。
例如设 X15,Y20,K2,B2则有且仅有下列三个数满足题意 172420 182421 202422
输入格式
第一行包含两个整数 X和 Y接下来两行包含整数 K和 B。
输出格式
只包含一个整数表示满足条件的数的个数。
数据范围 1≤X≤Y≤231−1 , 1≤K≤20 , 2≤B≤10
输入样例
15 20 2 2
输出样例
3
注意此题在dfs的过程中更新lim不能和普通的十进制类似对于普通的十进制我们写成 limit i a[pos] limit i up 但对于此题我们是枚举的每一位是否为 0 / 1 0/1 0/1所以lim的限制只能使用第一种形式。lim是对于我们枚举原数位进行限制但此处对于上界的确定
int uplim ? min(a[pos],1) : 1 ;所以只能使用第一种形式
#include bits/stdc.husing namespace std;
const int N 1e6 5;
typedef long long ll;
typedef pairll, ll pll;
typedef arrayll, 3 p3;
int mod 1e9 7;
const int maxv 4e6 5;ll dp[200][200];
int a[200];int l,r,k,b;ll dfs(int pos,int lim,int cnt)
{if(!pos) return cntk;if(!limdp[pos][cnt]!-1) return dp[pos][cnt];ll res0;int uplim ? min(a[pos],1) : 1 ;for(int i0;iup;i){if(cntik) continue;resdfs(pos-1,limia[pos],cnti);}if(!lim) dp[pos][cnt]res;return res;
}ll get(ll x)
{int len 0;while (x){a[len] x % b;x / b;}return dfs(len,1,0);
}void solve()
{cinlrkb;ll ansget(r)-get(l-1);coutansendl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t 1;// cin t;memset(dp, -1, sizeof dp);while (t--){solve();}system(pause);return 0;
}
