Codeforces817 C.Really Big Numbers(暴力)

    科技2022-09-16  127

    题意:

    给定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; }
    Processed: 0.009, SQL: 9