小红定义一个数是k-好数当且仅当这个数可以表示为若干个不同的k的幂之和。例如17是4-好数因为17 = 4² + 4º小红想知道在区间lr范围内共有多少个k-好数。第一行输入一个正整数q代表询问的次数。接下来的q行每行输入三个正整数lrk代表一次询问。输出q行每行输出一个整数代表该区间的k-好数的个数。用c++实现并使用动态规划算法。一个样例输入是 1 15 21 4 输出应该为4

#include #include using namespace std;

int main() { int q; cin >> q; while (q--) { int l, r, k; cin >> l >> r >> k; vector dp(r - l + 1); dp[0] = 1; for (int i = 1; i <= k; i++) { int power = 1; while (power <= r) { for (int j = r; j >= power; j--) { dp[j - l] += dp[j - power]; } power *= i; } } int ans = 0; for (int i = l; i <= r; i++) { if (dp[i - l] == 1) { ans++; } } cout << ans << endl; } return 0; }