题意:
给定n,s,问[1,n]中有多少个数x,满足x-f(x)>=s,其中f(x)表示x的数位和。
数据范围:n,s<=1e18
解法:
题目要求的是满足x-f(x)>=s的x的个数, 1.当x<s时,显然不满足条件(因为x还需要减去f(x))。 2.因为n,s<=1e18,那么数字位数不超过20位,就算所有数位都是9,也不超过200, 因此f(x)的最大值不超过200,所有满足x>s+200的x一定满足条件。
因为x<s时不用判断,x>s+200时也不用判断,那么只需要判断[s,s+200]范围内的数, 暴力即可(只有200)。
code:
#include<bits/stdc++.h>
using namespace std
;
#define int long long
int cal(int x
){
int ans
=0;
while(x
){
ans
+=x
%10;
x
/=10;
}
return ans
;
}
void solve(){
int n
,s
;cin
>>n
>>s
;
int ans
=0;
ans
+=max(0LL,n
-(s
+200));
for(int i
=s
;i
<=s
+200&&i
<=n
;i
++){
int t
=i
-cal(i
);
if(t
>=s
){
ans
++;
}
}
cout
<<ans
<<endl
;
}
signed main(){
int T
=1;
while(T
--){
solve();
}
return 0;
}