题解：AT_abc423_g [ABC423G] Small Multiple 2

· · 题解

题目大意

给你一个整数 K 与一个数字串 S，其中 1\leqslant K\leqslant10^9,1\leqslant|S|\leqslant5\times10^5。

需要你求出最小的整数 N，使得 N 是 K 的倍数且 N 在十进制下表示成的数字串包含了 S 作为子串。

解法

由于笔者过于蒟蒻，所以只能给出一个码量较小的算法。

我们设 K 的位数为 y。

那么考虑在 S 的后面补上 y 个数字，设那 y 个数字其转为十进制为整数 q。

那么组成的整数满足 S\times10^{y}+q\equiv0\pmod K，即 q\equiv-S\times10^{y}\pmod K。

显然 10^{y}\geqslant q，即 q 绝对存在。

所以答案 N 需满足位数小于等于 |S|+y。

那么我们设在 S 后放一个 f 位的十进制数，要求 K\geqslant10^f，前面放一个 y-f 位的十进制数（均可包含前导零）。

我们设放在 S 前的十进制数为 x，放在 S 后的十进制数为 z。

那么要使 z 存在需满足 -(10^{|S|+f}x+S\times10^f)\bmod K<10^f。

于是我们设 A=-10^{|S|+f}\bmod K,B=-S\times10^f\bmod K。

原式等于 (Ax+B)\bmod K<10^f。

由于 Ax+B=(Ax+B)\bmod K+K\lfloor{Ax+B\over K}\rfloor，那么如果上式成立，Ax+B-10^f=(Ax+B)\bmod K+K\lfloor{Ax+B\over K}\rfloor-10^f。

由于 (Ax+B)\bmod K<10^f，所以原式可变为

Ax+B-10^f=[(Ax+B)\bmod K+K-10^f]+K\left(\left\lfloor{Ax+B\over K}\right\rfloor-1\right)

即

\left\lfloor{Ax+B-10^f\over K}\right\rfloor=\left\lfloor{Ax+B\over K}\right\rfloor-1

所以

\left\lfloor{Ax+B\over K}\right\rfloor-\left\lfloor{Ax+B-10^f\over K}\right\rfloor=1

由于 x 越小，N 越小，所以我们需找到最小的 x 满足上式。

由于上式的值只有可能是 0/1，所以最小的 x 需满足

\sum_{i=0}^x\left\lfloor{Ax+B\over K}\right\rfloor-\left\lfloor{Ax+B-10^f\over K}\right\rfloor\geqslant1

二分查找 x 即可，式子求值用类欧几里得算法求解。

由于 B-10^f 有可能小于零，所以考虑将 B 统一加上 K。

取 \min 直接高精度求 \min。

::::info[Code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int k,cnt,n,len;
int as[N],ans[N],orz,ozr,bz[N];
string s;
void cmp(int len2){
    if(len2>len) return;
    if(len2<len){
        len=len2;
        for(int i=0;i<=len;i++) ans[i]=bz[i];
        return ;
    }
    for(int i=len;i>=0;i--){
        if(ans[i]<bz[i]) break;
        if(ans[i]>bz[i]){
            for(int i=0;i<=len;i++) ans[i]=bz[i];
            return ;
        }
    }
}
int f(int n,int a,int b,int c){
    if(n==-1) return 0;
    if(a==0) return (n+1)*(b/c);
    if(a>=c||b>=c) return (n+1)*n/2*(a/c)+(n+1)*(b/c)+f(n,a%c,b%c,c);
    int now=f((n*a+b)/c-1,c,c-1-b,a);
    return ((n*a+b)/c)*n-now;
}
bool chk(int len,int a,int b,int pw){
    int sum=f(len,a,b,k)-f(len,a,b-pw,k);
    if(sum>=1) return 1;
    else return 0;
}
void calc(int y,int c){
    int pw=pow(10,y);
    int a=(k-ozr*pw%k)%k;
    int b=(k-orz*pw%k)%k;
    int l=0,r=pow(10,c)-1,ans=0;
    while(l<=r){
        int mid=l+r>>1;
        if(chk(mid,a,b+k,pw)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    int ct=-1,d=(a*ans+b)%k;
    if(d>=pw) return;
    while(d) bz[++ct]=d%10,d/=10;
    while(ct+1<y) bz[++ct]=0;
    for(int i=n;i>=1;i--) bz[++ct]=as[i];
    while(ans) bz[++ct]=ans%10,ans/=10;
    cmp(ct);
}
void solve(){
    cin>>k>>s;
    n=s.size();
    orz=0,ozr=1;
    for(int i=0;i<n;i++) as[i+1]=s[i]-'0';
    for(int i=1;i<=n;i++) orz=(orz*10%k+as[i])%k,ozr=ozr*10%k;
    int x=k;cnt=0,len=1e7;
    while(x) cnt++,x/=10;
    for(int i=0;i<=cnt;i++) calc(i,cnt-i);
    for(int i=len;i>=0;i--) cout<<ans[i];
    cout<<"\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int _;
    cin>>_;
    while(_--) solve();
    return 0;
}

::::