Really Big Numbers CodeForces - 817C （数学规律+二分）

C. Really Big Numbers

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Ivan likes to learn different things about numbers, but he is especially interested in really big numbers. Ivan thinks that a positive integer number x is really big if the difference between x and the sum of its digits (in decimal representation) is not less than s. To prove that these numbers may have different special properties, he wants to know how rare (or not rare) they are — in fact, he needs to calculate the quantity of really big numbers that are not greater than n.

Ivan tried to do the calculations himself, but soon realized that it's too difficult for him. So he asked you to help him in calculations.

Input

The first (and the only) line contains two integers n and s (1 ≤ n, s ≤ 1018).

Output

Print one integer — the quantity of really big numbers that are not greater than n.

Examples

input

Copy

12 1

output

Copy

input

Copy

25 20

output

Copy

input

Copy

10 9

output

Copy

Note

In the first example numbers 10, 11 and 12 are really big.

In the second example there are no really big numbers that are not greater than 25 (in fact, the first really big number is 30: 30 - 3 ≥ 20).

In the third example 10 is the only really big number (10 - 1 ≥ 9).

中文题意：

给你一个数N和k，让你找出小于等于N的数x的数量，x满足这样的条件：

x减去x的每一位的数字sum和的结果大于等于k，我们设这个过程叫F（x），即F（x）= x - sumdig(x)

思路：

先手写一部分数字看下他们的结果。

1-1=0
2-2=0
10-1=9
11-2=9
12-3=9
13-4=9
14-5=9
15-6=9
16-7=9
17-8=9
18-9=9
19-10=9
20-2=18
21-3=18
29-11=18
30-3=27
80-8=72
90-9=81
+9
99-18=81
100-1=99
110-2=108
120-3=117

发现没有明确的直接的数学公式可以得出满足条件最小的数num，

我们只所以找num，是因为得出num可以直接根据num和N的关系来算出结果，

num就是最小的满足条件的那个数。

但是通过上面的一些数字可以发现，F（x）的值是随着x单调递增的。

SPEAKING OF 单调递增，显然我们可以想到二分，

即二分出那个num，然后直接得出答案。

具体细节见我的code:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#define sz(a) int(a.size())

#define all(a) a.begin(), a.end()

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define gg(x) getInt(&x)

#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;

using namespace std;

typedef long long ll;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

ll powmod(ll a,ll b,ll MOD){ll ans=;while(b){if(b%)ans=ans*a%MOD;a=a*a%MOD;b/=;}return ans;}

inline void getInt(int* p);

const int maxn=;

const int inf=0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

ll n;

ll k;

ll check(ll x)

{

    ll cnt=0ll;

    ll f=x;

    while(x)

    {

        cnt+=(x%);

        x/=;

    }

    return f-cnt;

}

int main()

{

    cin>>n>>k;

    ll l=0ll;

    ll r=n;

    ll mid;

    ll num=1e18;

    num++;

    while(l<=r)

    {

        mid=(l+r)/2ll;

        if(check(mid)>=k)

        {

            num=mid;

            r=mid-;

        }else

        {

            l=mid+;

        }

    }

//    db(num);

    ll ans=max(0ll,n-num+);

    cout<<ans<<endl;

    return ;

}

inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '');

        while ((ch = getchar()) >= '' && ch <= '') {

            *p = *p *  - ch + '';

        }

    }

    else {

        *p = ch - '';

        while ((ch = getchar()) >= '' && ch <= '') {

            *p = *p *  + ch - '';

        }

    }

}

巴特西

Really Big Numbers CodeForces - 817C （数学规律+二分）

最新文章

热门文章