盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 5085 Counting problem(暴力+HashTable)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=5085

题意

定义f(n,k) = 各位数字的k次方和。例如f(305, 2) = 5^2 + 0^2 + 3^2 = 34
给定a,b,k,s。求[a,b]区间内满足f(n,k)=s的数字个数
1≤a≤b≤999999999; 1≤k≤15; 1≤S≤10^16

思路

把n分为按照长度分为两半部分,前半部分暴力枚举,后半部分加入hash表中,这样将复杂度降到sqrt(n)hash表中记录每种和的情况数。要注意一些细节:

  1. 不妨设一个B=10000,如果a,b都小于B。直接枚举即可
  2. 当b大于B时,ahead = (a-1) / B, atail = a % B bhead = b / B, btail = b % B
    将0~B-1的数字加入hash表时,记录一下以ahead开头符合条件的个数resa,再记录一下以bhead开头的符合条件的resb
    之后枚举[ahead, bhead), 符合条件的累加到resb中,最后答案即为resb-resa

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define debug puts("=====================");
using namespace std;
typedef long long ll;
//Hash Table
#define pii pair<ll, ll>
#define fi first
#define se second
#define MAXN 10010
#define mod 40007
struct HashKey {
ll key;
int nxt, cnt;
} e[MAXN];
int link1[MAXN * 4], p, k;
ll s;
void init() {
memset(link1, -1, sizeof(link1));
p = 0;
}
void add(ll key) {
e[p].key = key;
e[p].cnt = 1;
int modKey = key % mod;
if (modKey < 0) modKey += mod;
e[p].nxt = link1[modKey];
link1[modKey] = p++;
}
int Find(ll key) {
int modKey = key % mod;
if (modKey < 0) modKey += mod;
for (int i = link1[modKey]; i != -1; i = e[i].nxt) {
if (e[i].key == key) {
return i;
}
}
return -1;
}
ll calc(int x) {
ll ans = 0, tmp = 1;
while(x) {
int t = x % 10;
x /= 10;
tmp = 1;
for (int i = 0; i < k; i++) tmp *= t;
ans += tmp;
}
if (ans > s) return -1;
return ans;
}
void solve(int x) {
ll ans = calc(x);
if (ans > s || ans == -1) return ;
int k = Find(ans);
if (k == -1) add(ans);
else e[k].cnt++;
}
int work(int ahead) {
ll ans = calc(ahead);
if (ans == -1) return 0;
if (ans <= s) {
int x = Find(s - ans);
if (x != -1) return e[x].cnt;
}
return 0;
}
int main () {
ll a, b;
int B = 10000;
while(~scanf("%I64d%I64d%d%I64d", &a, &b, &k, &s)) {
if (b < B) {
int res = 0;
for (int i = a; i <= b; i++) {
if (calc(i) == s) res++;
}
printf("%d\n", res);
continue;
}
init();
int bhead = b / B, btail = b % B;
int ahead = (a - 1) / B, atail = (a - 1) % B;
ll resa = 0, resb = 0;
if (atail < btail) {
for (int i = 0; i <= atail; i++) solve(i);
resa = work(ahead);
for (int i = atail + 1; i <= btail; i++) solve(i);
resb = work(bhead);
for (int i = btail + 1; i < B; i++) solve(i);
} else {
for (int i = 0; i <= btail; i++) solve(i);
resb = work(bhead);
for (int i = btail + 1; i <= atail; i++) solve(i);
resa = work(ahead);
for (int i = atail + 1; i < B; i++) solve(i);
}
for (int i = ahead; i < bhead; i++) resb += work(i);
printf("%I64d\n", resb - resa);
}
return 0;
}