Codeforces-1485A Add and Divide


Problem

Portal


Thoughts

  1. b加1次1,那么后面的除法操作必然少>=1次,总操作次数必然减小。
  2. 我们思考最后答案最多为$log_2^{1e9}+1=30$次($a=1e9, b=1$),那么也就是说我们加法操作最多只需要加50次即可。

Accepted Code

#include <bits/stdc++.h>
#define endl '\n' 
#define int long long

using namespace std;

signed main()
{
    int T; cin >> T;
    while(T -- )
    {
        int a, b, cnt = 0, res = 0x3f3f3f3f;
        cin >> a >> b;
        if(b == 1) b ++ , cnt ++ ;
        for(int i = b ; i <= b+50 ; i ++ )
        {
            int ta = a, tp = i-b;
            while(ta)
            {                
                ta /= i;
                tp ++ ;
            }
            res = min(res, cnt+tp);
        }
        cout << res << endl;
    }

    return 0;
}

Author: Mrhh
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Mrhh !
评论
  TOC