本文共 1141 字，大约阅读时间需要 3 分钟。
kk说是16年CCPC杭州赛的银牌题
给定 x , K ( x < 1 0 9 , 1 ≤ K ≤ 9 ) x,K(x<10^9,1≤K≤9) x,K(x<109,1≤K≤9)求满足 x = f ( y , K ) − y x=f(y, K)-y x=f(y,K)−y的所有正整数y的数量。
f ( y , K ) = ∑ z in every digits of y z K ( f ( 233 , 2 ) = 2 2 + 3 2 + 3 2 = 22 ) f(y, K)=\sum_{z \text { in every digits of } y} z^{K}\left(f(233,2)=2^{2}+3^{2}+3^{2}=22\right) f(y,K)=z in every digits of y∑zK(f(233,2)=22+32+32=22) - 定y的范围， y < 1 0 10 y<10^{10} y<1010
- 由于每个数字对f的贡献独立，所以可以折半求解。令 y = 1 0 5 ∗ a + b y=10^5*a+b y=105∗a+b，则 x − ( f ( a , K ) − 1 0 5 ∗ a ) = f ( b , K ) − b x-(f(a,K)-10^5*a)=f(b,K)-b x−(f(a,K)−105∗a)=f(b,K)−b。先求出1e5以内所有的 f ( b , K ) − b f(b,K)-b f(b,K)−b，然后进行枚举高5位a， v a l = x − ( f ( a , K ) − 1 0 5 ∗ a ) val=x-(f(a,K)-10^5*a) val=x−(f(a,K)−105∗a)，二分查找对应的 f ( b , K ) − b f(b,K)-b f(b,K)−b的数量。
- 注意：当 x = 0 x=0 x=0时，会把0算进去。题目求正整数，减去1。
#include #define endl '\n'using namespace std;#define debug(_x) cout<<#_x<<": "<<_x< >=1; } return res;}void init(){ int e5=100000; for(int j=1;j<=9;++j){ for(int i=1;i >T; for(int casei=1;casei<=T;++casei){ cin>>x>>k; cout<<"Case #"< <<": "<
转载地址：http://ggkzi.baihongyu.com/