题意:
有一个函数f(y, k) = y的每个十进制位上的数字的k次幂之和
给x, k 求 有多少个y满足 x = f(y, k) - y
思路:
(据说这叫中途相遇法?)
由于 x >= 0 所以 显然y最多也不会超过10位数
把一个数拆成前5位 和 后5位
即找有多少对(a, b)满足 x = a + b
把所有的后五位预处理出来,然后再找前五位。
找的时候用二分,mapT了。。可能组数太多了吧。
具体看代码
const int maxn = + ; LL num[maxn];
int x, k;
LL p[][];
LL sum[maxn];
int idx; void init()
{
memset(sum, , sizeof(sum));
idx = ; scanf("%d%d", &x, &k);
for (int i = ; i < ; i++)
{
int t = i;
while (t)
{
sum[i] += p[t % ][k];
t /= ;
}
num[idx++] = sum[i] - i;
}
sort(num, num + idx);
} void solve()
{
LL t = ;
LL ans = ;
for (LL i = ; i < ; i++)
{
t = sum[i] - i * ;
int f = lower_bound(num, num + idx, x - t) - num;
while (num[f] == x - t && f < idx)
{
f++;
ans++;
}
}
printf("%lld\n", ans);
} int main()
{
for (int i = ; i < ; i++)
{
p[i][] = ;
for (int j = ; j < ; j++)
{
p[i][j] = p[i][j-] * i;
}
}
int T, kase = ;
scanf("%d", &T);
while (T--)
{
printf("Case #%d: ", ++kase);
init();
solve();
}
return ;
}