风，吹来奏折的香味！愿奇迹降临此间！

FutaRimeWoawaSete · 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;
}