自动搬运

查看原文

来自洛谷，原作者为

	FutaRimeWoawaSete Dear the f**king destiny!

搬运于2025-08-24 22:36:19，当前版本为作者最后更新于2023-01-16 11:05:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8140 sol

所以是 corner 题。

我们考虑枚举答案，将当前的数分为前半部分和后半部分。后半部分显然是长度为 $\text{ans}$ 个 $\text d$ 的字符串。

对于其求模数对 $\text b$，那么前半部分对于 $\text b$ 的模数 $\text p$ 也可以知晓，设前半部分可以表示成 $\text{10}^{\text v} \times \text x$ 的形式，令 $\text a = \text{10} ^ {\text v},\text c = \text p$，我们使用同余方程求解 $\text{ax} \equiv \text c (\text{mod} \ \text b)$ 的最小整数解 $\text x$，然后比较一下范围超没有即可判断，在这里直接暴力 $\text O(\log_{\text{10}} \text a ^ 2)$ 判断即可。

corner：

• 当 $\text d = \text 0$ 若 $\text x = \text 0$，要将 $\text x$ 加到正整数；

• 可能要特判长度为总长时的情况，我不判反正挂了；

/*
也就 1e4，暴力比算了。 
*/
#include "bits/stdc++.h"
using namespace std;
const int Len = 1e5 + 5;
int b,d,a,mod,mt[Len];
inline int pt(int x)
{
	int rs = 0;
	while(x && x % 10 == d) 
	{
		rs ++;
		x /= 10;
	}
	return rs;
}
char s[Len];
const int Inf = 1e7;
int gcd(int a,int b)
{
	if(!b) return a;
	return gcd(b , a % b);
}
int exgcd(int a,int b,int &x,int &y) 
{
  	if(!b) 
	{
    	x = 1;
    	y = 0;
    	return a;
	}
	int d = exgcd(b , a % b , x , y);
	int t = x;
	x = y;
	y = t - (a / b) * y;
	return d;
}
int get(int a,int b,int mod)
{
	int GCD = gcd(a , mod);
	if(b % GCD) return -1;
	int A = a / GCD , B = b / GCD , MOD = mod / GCD , x , y;
	int rcd = exgcd(A , MOD , x , y);
	x = 1ll * x * B % MOD;
	x %= MOD;
	if(x < 0) x += MOD;
	x %= MOD;
	if(!d && x == 0) x += MOD;
	return x;	
}
int main()
{
	//freopen("03.in","r",stdin);
	scanf("%d %d",&b,&d);scanf("%s",s + 1);
	mod = b;mt[0] = 1;int len = strlen(s + 1);
	for(int i = 1 ; i <= len ; i ++) mt[i] = 1ll * mt[i - 1] * 10 % mod;
	int as = 0 , sm = 0;
	//printf("!%d\n",len);
	for(int i = 1 ; i < len ; i ++) 
	{
		sm = 1ll * sm * 10 % mod + d , sm %= mod;
		int gt = get(mt[i] , mod - sm , mod) , b1 = 0 , b2 = 0;
		if(gt == -1) continue;
		//printf("%d %d %d %d\n",i,gt,mod - sm,mt[i]);
		if(len - i >= 7) b1 = 2;
		else
		{
			int x = 0;
			for(int j = 1 ; j <= len - i ; j ++) x = x * 10 + (s[j] - '0');
			if(x > gt) b1 = 2;
			else if(x == gt) b1 = 1;
			else b1 = 0;
			//printf("%d %d\n",i,b1);
		}
		//if(len == i) b1 = 1;
		b2 = 1;
		for(int j = len - i + 1 ; j <= len ; j ++) 
		{
			if(s[j] - '0' != d)
			{
				if(s[j] - '0' < d) b2 = 0;
				else b2 = 2;
				break;
			}
		}
		if(b1 == 2 || (b1 == 1 && b2)) as = i;
	}
	int ss = 0 , bl = 1;
	for(int i = 1 ; i <= len ; i ++) ss = (1ll * ss * 10 + d) % mod;
	for(int i = 1 ; i <= len ; i ++)
	{
		if(d != s[i] - '0')
		{
			if(d < s[i] - '0') bl = 2;
			else bl = 0;
			break;
		}
	} 
	//printf("%d %d %d %d\n",d,ss,bl,len);
	if(d && !ss && bl) as = len;
	printf("%d\n",as);
	return 0;
}