记录编号	608211	评测结果	AAAAAAAAAA
题目名称	4077.小b爱取模	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	2.199 s
提交时间	2025-10-24 15:05:03	内存使用	90.62 MiB

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

const int N = 1e7+10;

int res,a[N],k,n,b[N],s[N];
char c[N];

signed main(){
	freopen("changgao_modulo.in","r",stdin);
	freopen("changgao_modulo.out","w",stdout);
	cin>>k;
	scanf("%s",c+1);
	c[0]='0';
	n=strlen(c+1);
	for(int i=1;i<=n;i++){
		a[i]=c[i]-'0'; 
	}
	for(int i=1;i<=n;i++){
		b[i]=(k-a[i]+a[i-1])%k;
	}
	for(int i = 1;i <= n;i++){
		s[i]=s[i-1]+b[i];
	}
	for(int i=k-1;i>=0;i--){
		int minn=1e18;
		for(int j=n;j>=1;j--){
			minn=min(minn,s[j]);
			if(minn>=k&&b[j]==i){
				minn-=k;
				b[j]-=k;
			}
		}
		for(int j=1;j<=n;j++)s[j]=s[j-1]+b[j];
	} 
	for(int i=1;i<=n;i++)res+=max(0,b[i]);
	printf("%lld",res); 
	return 0;
}