1.題目連結。題目定義了一個f(y,k)函數，f(y,k)就是y每個數位的k次方求和。x=f(y,k)-y.現在已經知道了x.k.問有多少種y滿足條件。
首先x<1e9,說明y不是很大，int範圍内的資料。最多時10位資料。現在我們假設y是10位數，然後分别考慮高五位和低五位。那麼y一定可以被寫成:a+b*(1e5).帶入原方程:
随便整理一下：
其中，a,b是小于1e5的數,k<=9.是以可以提前把f(a,k)全部找出來，我們預處理右邊，對于左邊upper和lower一下，就可以找到中間有多少滿足方程的解。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define ll long long
ll f[11][11];
ll h[N][11];
ll s[N];
void init()
{
for (ll i = 0; i <= 9; i++)
{
f[i][0] = 1;
for (ll j = 1; j <= 9; j++)
{
f[i][j] = f[i][j - 1] * i;
}
}
memset(h, 0, sizeof(h));
for (ll i = 0; i < N; i++)
{
for (ll j = 1; j <= 9; j++)
{
ll tem = i;
while (tem> 0)
{
ll flag = tem % 10;
tem /= 10;
h[i][j] += f[flag][j];
}
}
}
}
const int _1e5 = 1e5;
ll solve(ll x, ll k)
{
for (ll i = 0; i < N; i++)s[i] = h[i][k] - i*_1e5;
sort(s, s + N);
ll ans = 0;
for (int i = 0; i < N; i++)
{
ll tem = h[i][k] - i;
ans += upper_bound(s, s + N, x - tem) - lower_bound(s, s + N, x - tem);
}
return ans-(x==0);
}
int main()
{
int T;
scanf("%d", &T);
init();
for (int ca = 1; ca <= T; ca++)
{
ll x, k;
scanf("%lld%lld", &x, &k);
ll ans = solve(x, k);
printf("Case #%d: %lld\n", ca, ans);
}
}