題意：
有一個函數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了。。可能組數太多了吧。

具體看代碼

?

1 const int maxn = 100000 + 10; 2 3 LL num[maxn]; 4 int x, k; 5 LL p[10][10]; 6 LL sum[maxn]; 7 int idx; 8 9 void init() 10 { 11 memset(sum, 0, sizeof(sum)); 12 idx = 0; 13 14 scanf("%d%d", &x, &k); 15 for (int i = 1; i < 100000; i++) 16 { 17 int t = i; 18 while (t) 19 { 20 sum[i] += p[t % 10][k]; 21 t /= 10; 22 } 23 num[idx++] = sum[i] - i; 24 } 25 sort(num, num + idx); 26 } 27 28 void solve() 29 { 30 LL t = 0; 31 LL ans = 0; 32 for (LL i = 0; i < 100000; i++) 33 { 34 t = sum[i] - i * 100000; 35 int f = lower_bound(num, num + idx, x - t) - num; 36 while (num[f] == x - t && f < idx) 37 { 38 f++; 39 ans++; 40 } 41 } 42 printf("%lld\n", ans); 43 } 44 45 int main() 46 { 47 for (int i = 1; i < 10; i++) 48 { 49 p[i][0] = 1; 50 for (int j = 1; j < 10; j++) 51 { 52 p[i][j] = p[i][j-1] * i; 53 } 54 } 55 int T, kase = 0; 56 scanf("%d", &T); 57 while (T--) 58 { 59 printf("Case #%d: ", ++kase); 60 init(); 61 solve(); 62 } 63 return 0; 64 }

?

轉載于:https://www.cnblogs.com/liangyongrui/p/6035676.html

總結

以上是生活随笔為你收集整理的HDU 5936 Difference的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。