专栏文章

题解：AT_abc423_g [ABC423G] Small Multiple 2

eemmoy
AT_abc423_g题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minsq84m
此快照首次捕获于
2025/12/02 07:44
3 个月前
此快照最后确认于
2025/12/02 07:44
3 个月前
查看原文

题目大意

给你一个整数 KK 与一个数字串 SS，其中 1⩽K⩽109,1⩽∣S∣⩽5×1051\leqslant K\leqslant10^9,1\leqslant|S|\leqslant5\times10^5。
需要你求出最小的整数 NN，使得 NN 是 KK 的倍数且 NN 在十进制下表示成的数字串包含了 SS 作为子串。

解法

由于笔者过于蒟蒻，所以只能给出一个码量较小的算法。
我们设 KK 的位数为 yy。
那么考虑在 SS 的后面补上 yy 个数字，设那 yy 个数字其转为十进制为整数 qq。
那么组成的整数满足 S×10y+q≡0(modK)S\times10^{y}+q\equiv0\pmod K，即 q≡−S×10y(modK)q\equiv-S\times10^{y}\pmod K。
显然 10y⩾q10^{y}\geqslant q，即 qq 绝对存在。
所以答案 NN 需满足位数小于等于 ∣S∣+y|S|+y。
那么我们设在 SS 后放一个 ff 位的十进制数，要求 K⩾10fK\geqslant10^f，前面放一个 y−fy-f 位的十进制数（均可包含前导零）。
我们设放在 SS 前的十进制数为 xx，放在 SS 后的十进制数为 zz。
那么要使 zz 存在需满足 −(10∣S∣+fx+S×10f) mod K<10f-(10^{|S|+f}x+S\times10^f)\bmod K<10^f。
于是我们设 A=−10∣S∣+f mod K,B=−S×10f mod KA=-10^{|S|+f}\bmod K,B=-S\times10^f\bmod K。
原式等于 (Ax+B) mod K<10f(Ax+B)\bmod K<10^f。
由于 Ax+B=(Ax+B) mod K+K⌊Ax+BK⌋Ax+B=(Ax+B)\bmod K+K\lfloor{Ax+B\over K}\rfloor，那么如果上式成立，Ax+B−10f=(Ax+B) mod K+K⌊Ax+BK⌋−10fAx+B-10^f=(Ax+B)\bmod K+K\lfloor{Ax+B\over K}\rfloor-10^f。
由于 (Ax+B) mod K<10f(Ax+B)\bmod K<10^f，所以原式可变为
Ax+B−10f=[(Ax+B) mod K+K−10f]+K(⌊Ax+BK⌋−1)Ax+B-10^f=[(Ax+B)\bmod K+K-10^f]+K\left(\left\lfloor{Ax+B\over K}\right\rfloor-1\right)
即
⌊Ax+B−10fK⌋=⌊Ax+BK⌋−1\left\lfloor{Ax+B-10^f\over K}\right\rfloor=\left\lfloor{Ax+B\over K}\right\rfloor-1
所以
⌊Ax+BK⌋−⌊Ax+B−10fK⌋=1\left\lfloor{Ax+B\over K}\right\rfloor-\left\lfloor{Ax+B-10^f\over K}\right\rfloor=1
由于 xx 越小，NN 越小，所以我们需找到最小的 xx 满足上式。
由于上式的值只有可能是 0/10/1，所以最小的 xx 需满足
∑i=0x⌊Ax+BK⌋−⌊Ax+B−10fK⌋⩾1\sum_{i=0}^x\left\lfloor{Ax+B\over K}\right\rfloor-\left\lfloor{Ax+B-10^f\over K}\right\rfloor\geqslant1
二分查找 xx 即可，式子求值用类欧几里得算法求解。
由于 B−10fB-10^f 有可能小于零，所以考虑将 BB 统一加上 KK。
取 min⁡\min 直接高精度求 min⁡\min。
CodeCPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...