C++(g++ 7.5.0) 解法, 执行用时: 74ms, 内存消耗: 576K, 提交时间: 2022-12-16 20:19:55

#include <bits/stdc++.h>
using namespace std;

long long val[20];

void solve() {
    long long n, m;
    scanf("%lld%lld", &n, &m);
    m --;
    for(long long i = 1, cnt = 10; i <= 19; i ++) {
        if(m > cnt) val[i] = cnt - cnt / 10;
        else val[i] = max(0ll, m + 1 - cnt / 10);
        cnt *= 10;
    }
    long long ans = 2e18;
    for(int i = 19; i >= 1; i --) {
        long long left = n, tans = 0;
        for(int j = i - 1; left > 0 && j >= 1; j --) {
            long long   cnti = min(left / i, val[i]),
                        cntj = min((left - cnti * i) / j, val[j]);                        
            for(int t = 1; cnti >= 0 && cntj <= val[j] && t <= 30; t ++) {
                if(left == cnti * i + cntj * j) ans = min(ans, tans + cnti + cntj);
                cntj ++;
                if(left < cnti * i + cntj * j)
                    cnti --;
            }
            left -= val[j] * j;
            tans += val[j];
        }
    }
    if(ans > m) puts("GingerNB");
    else printf("%lld\n", ans);
}

int main() {
    int T;
    scanf("%d", &T);
    while(T --)
        solve();
}

C++(clang++ 11.0.1) 解法, 执行用时: 217ms, 内存消耗: 588K, 提交时间: 2022-12-16 20:51:46

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll c[30],n,m;
ll d[30];
ll chk(int l,int r){
    for(int i=1;i<=20;i++)c[i]=d[i];
    ll tot=0,nw=0;
    for(int i=r-1;i>=l;i--){tot+=c[i]*i,nw+=c[i];if(tot>n)return 1ll<<61;}
    ll nd=n-tot,g=__gcd(l-1,r);
    if(nd%g)return 1ll<<61;
    while(nd%(l-1))c[r]--,nw++,nd-=r;
    if(nd<0||c[r]<0)return 1ll<<61;
    ll rt=(l-1)/g;
    c[r]/=rt,c[r]*=rt;
    ll rtake=min(nd/((l-1)*r/g)*rt,c[r]);
    nw+=rtake,nd-=rtake*r;
    nw+=nd/(l-1);
    c[l-1]-=nd/(l-1);
    if(c[l-1]<0)return 1ll<<61;
    return nw;
}
void solve(){
    memset(c,0,sizeof c);cin>>n>>m;
    ll nw=1;
    for(int i=0;i<=18;i++)c[i]=min(m,nw),nw*=10;
    for(int i=18;i;i--)c[i]-=c[i-1];
    ll rs=1ll<<61;c[0]=0;for(int i=1;i<=20;i++)d[i]=c[i];
    for(int l=2;l<=18;l++)for(int r=l;r<=18;r++)rs=min(rs,chk(l,r));
    if(rs==1ll<<61)cout<<"GingerNB\n";
    else cout<<rs<<'\n';
}

int main(){
    int T;cin>>T;
    while(T--)solve();
}