算法分析

$\overbrace{11 \cdots 1}^N = \frac{10^N-1}{9}$

于是，原同余方程等价于 $10^N \equiv 9k+1 \pmod p$

求最小的 $N$ 就是 $\mathbf{BSGS}$ 的板题了。

这题唯一的坑点就是会炸long long（因为模数就是 long long），解决方法是龟速乘或开 int128

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;
using i128 = __int128_t;

ll mod;
//const int mod = 998244353;
//const int mod = 1000000007;
struct mint {
    i128 x;
    mint(ll x=0):x((x%mod+mod)%mod) {}
    mint operator-() const {
        return mint(-x);
    }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const {
        return mint(*this) += a;
    }
    mint operator-(const mint a) const {
        return mint(*this) -= a;
    }
    mint operator*(const mint a) const {
        return mint(*this) *= a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint a) {
        return *this *= a.inv();
    }
    mint operator/(const mint a) const {
        return mint(*this) /= a;
    }
};

int main() {
    ll k;
    cin >> k >> mod;

    ll m = sqrt(mod)+1;
    map<i128, ll> mp;
    mint b = k*9+1;
    rep(i, m) {
        mp[b.x] = i;
        b *= 10;
    }

    mint a = mint(10).pow(m);
    mint c = 1;
    for (int i = 1; i <= m; ++i) {
        c *= a;
        if (mp.count(c.x)) {
            cout << i*m-mp[c.x] << '\n';
            return 0;
        }
    }

    return 0;
}