思路与算法

题目要求从第1次幂开始循环，而不是允许先经过一段前缀后才循环。把模10^k分成互质的模2^k、模5^k。若0<v_p(n)<k，则 n 的幂在模p^k下的估值严格增长直到变为0，故不存在纯循环；若 v_p(n)≥k，该分量从一开始就是0；若 v_p(n)=0，则由欧拉定理存在乘法周期。两分量都可循环时，4·10^(k−1)一定是公共周期。以它作为 L，反复尝试把 L 除以2或5；若 n^(L/p+1)≡n (mod10^k) 则接受缩短。幂使用快速幂，乘法只保留末k位。

正确性说明

纯循环意味着 n^(L+1)≡n，乘以n^(a−1)便能推出所有a≥1都重复，因此该等式是充要条件。对于p进估值处于1..k−1的n，任何L≥1都会使 n^(L+1)−n 的估值仍为v_p(n)<k，故不可能成立。其余分量为恒0或单位群元素，欧拉定理给出公共上界周期。最小周期整除任意一个周期，而初始周期只有素因子2和5；每次合法除因子仍保留周期，直到两因子均无法再除时只能是最小周期。

复杂度

令 k 为保留的十进制位数，初始周期数位 O(k)、二进制位数 O(k)。预处理估值 O(k²)，共 O(k) 次除因子测试，每次快速幂 O(k) 次乘法，截断竖式乘法 O(k²)，故上界 O(k⁴) 位运算时间，辅助空间 O(k)。标程按每4位一组压缩数位以降低常数；k≤100。

易错点

例如2的后两位最终会出现循环，但不是从2¹开始，因此答案必须−1。不能无条件求互质乘法阶。n 本身可有100位，周期也可很大，不能转64位整数。模10^k时保留前导0的含义是同余，输出周期无需补零。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct cpp_int {
    string s;
    bool neg;
    cpp_int(long long v = 0) : s(to_string(v)), neg(v < 0) {
        if (neg)
            s.erase(s.begin());
    }
    void norm() {
        auto p = s.find_first_not_of('0');
        s = p == string::npos ? "0" : s.substr(p);
        if (s == "0")
            neg = false;
    }
    static int cmpabs(const cpp_int &a, const cpp_int &b) {
        if (a.s.size() != b.s.size())
            return a.s.size() < b.s.size() ? -1 : 1;
        return a.s == b.s ? 0 : a.s < b.s ? -1 : 1;
    }
    friend bool operator<(const cpp_int &a, const cpp_int &b) {
        if (a.neg != b.neg)
            return a.neg;
        int c = cmpabs(a, b);
        return a.neg ? c > 0 : c < 0;
    }
    friend bool operator==(const cpp_int &a, const cpp_int &b) {
        return a.neg == b.neg && a.s == b.s;
    }
    friend bool operator!=(const cpp_int &a, const cpp_int &b) {
        return !(a == b);
    }
    friend bool operator>(const cpp_int &a, const cpp_int &b) {
        return b < a;
    }
    friend bool operator<=(const cpp_int &a, const cpp_int &b) {
        return !(b < a);
    }
    friend bool operator>=(const cpp_int &a, const cpp_int &b) {
        return !(a < b);
    }
    cpp_int operator-() const {
        cpp_int r = *this;
        if (r.s != "0")
            r.neg = !r.neg;
        return r;
    }
    friend cpp_int operator+(const cpp_int &a, const cpp_int &b) {
        cpp_int r;
        r.s.clear();
        int carry = 0;
        if (a.neg == b.neg) {
            int i = (int)a.s.size() - 1, j = (int)b.s.size() - 1;
            while (i >= 0 || j >= 0 || carry) {
                int v = carry + (i >= 0 ? a.s[i--] - '0' : 0) + (j >= 0 ? b.s[j--] - '0' : 0);
                r.s += char('0' + v % 10);
                carry = v / 10;
            }
            r.neg = a.neg;
        } else {
            const cpp_int *x = &a, *y = &b;
            if (cmpabs(a, b) < 0)
                swap(x, y);
            int i = (int)x->s.size() - 1, j = (int)y->s.size() - 1;
            while (i >= 0) {
                int v = x->s[i--] - '0' - carry - (j >= 0 ? y->s[j--] - '0' : 0);
                carry = v < 0;
                if (carry)
                    v += 10;
                r.s += char('0' + v);
            }
            r.neg = x->neg;
        }
        reverse(r.s.begin(), r.s.end());
        r.norm();
        return r;
    }
    friend cpp_int operator-(const cpp_int &a, const cpp_int &b) {
        return a + (-b);
    }
    friend cpp_int operator*(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long carry = 0;
        long long z = b;
        if (z < 0)
            z = -z;
        for (int i = (int)a.s.size() - 1; i >= 0; i--) {
            carry += (a.s[i] - '0') * z;
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        while (carry) {
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        reverse(r.s.begin(), r.s.end());
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    friend cpp_int operator/(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long rem = 0, z = b;
        if (z < 0)
            z = -z;
        for (char c : a.s) {
            rem = rem * 10 + c - '0';
            r.s += char('0' + rem / z);
            rem %= z;
        }
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    cpp_int &operator+=(const cpp_int &b) {
        *this = *this + b;
        return *this;
    }
    cpp_int &operator-=(const cpp_int &b) {
        *this = *this - b;
        return *this;
    }
    cpp_int &operator*=(int b) {
        *this = *this * b;
        return *this;
    }
    friend istream &operator>>(istream &in, cpp_int &a) {
        string v;
        if (in >> v) {
            a.neg = v[0] == '-';
            if (v[0] == '-' || v[0] == '+')
                v.erase(v.begin());
            a.s = v;
            a.norm();
        }
        return in;
    }
    friend ostream &operator<<(ostream &out, const cpp_int &a) {
        if (a.neg)
            out << '-';
        return out << a.s;
    }
};

cpp_int fromString(string s) {
    cpp_int a;
    a.neg = !s.empty() && s[0] == '-';
    if (!s.empty() && (s[0] == '-' || s[0] == '+'))
        s.erase(s.begin());
    a.s = s;
    a.norm();
    return a;
}
cpp_int absBig(cpp_int a) {
    a.neg = false;
    return a;
}
cpp_int pow10(size_t n) {
    cpp_int a;
    a.s = "1" + string(n, '0');
    return a;
}
cpp_int operator*(const cpp_int &a, const cpp_int &b) {
    vector<long long> d(a.s.size() + b.s.size());
    for (int i = (int)a.s.size() - 1; i >= 0; --i)
        for (int j = (int)b.s.size() - 1; j >= 0; --j)
            d[i + j + 1] += (a.s[i] - '0') * (b.s[j] - '0');
    for (int i = (int)d.size() - 1; i > 0; --i) {
        d[i - 1] += d[i] / 10;
        d[i] %= 10;
    }
    cpp_int c;
    c.s.clear();
    for (auto x : d)
        c.s += char('0' + x);
    c.neg = a.neg != b.neg;
    c.norm();
    return c;
}
pair<cpp_int, cpp_int> divmod(cpp_int a, cpp_int b) {
    bool sign = a.neg != b.neg, negrem = a.neg;
    a.neg = b.neg = false;
    cpp_int q, rem;
    q.s.clear();
    cpp_int mul[10];
    for (int i = 0; i < 10; ++i)
        mul[i] = b * i;
    for (char z : a.s) {
        rem = rem * 10 + (z - '0');
        int lo = 0, hi = 9;
        while (lo < hi) {
            int mi = (lo + hi + 1) / 2;
            if (mul[mi] <= rem)
                lo = mi;
            else
                hi = mi - 1;
        }
        q.s += char('0' + lo);
        rem -= mul[lo];
    }
    q.neg = sign;
    q.norm();
    rem.neg = negrem;
    rem.norm();
    return {q, rem};
}
cpp_int floorDiv(cpp_int a, const cpp_int &b) {
    auto z = divmod(a, b);
    if (a.neg && z.second != 0)
        z.first -= 1;
    return z.first;
}
cpp_int rootBig(const cpp_int &a) {
    cpp_int root, rem;
    string s = a.s;
    if (s.size() % 2)
        s = "0" + s;
    for (size_t i = 0; i < s.size(); i += 2) {
        rem = rem * 100 + (s[i] - '0') * 10 + s[i + 1] - '0';
        int x = 9;
        while ((root * 20 + x) * x > rem)
            --x;
        rem -= (root * 20 + x) * x;
        root = root * 10 + x;
    }
    return root;
}
string fixedBig(cpp_int rounded, int digits) {
    bool neg = rounded.neg;
    string s = rounded.s;
    while (s.size() <= (size_t)digits)
        s = "0" + s;
    if (digits)
        s.insert(s.size() - digits, ".");
    return (neg ? "-" : "") + s;
}
cpp_int roundedRational(cpp_int a, cpp_int b) {
    bool neg = a.neg != b.neg;
    a.neg = b.neg = false;
    auto q = divmod(a, b);
    if (q.second * 2 >= b)
        q.first += 1;
    q.first.neg = neg && q.first != 0;
    return q.first;
}

const int BASE = 10000;
struct ModInt {
    vector<int> a;
};
int digits, lim, lastBase;
ModInt parseMod(string s) {
    ModInt x;
    x.a.assign(lim, 0);
    for (int i = (int)s.size(), j = 0; i > 0 && j < lim; i -= 4, ++j)
        x.a[j] = stoi(s.substr(max(0, i - 4), min(4, i)));
    x.a.back() %= lastBase;
    return x;
}
ModInt multiply(const ModInt &x, const ModInt &y) {
    vector<unsigned long long> t(lim + 1);
    for (int i = 0; i < lim; ++i)
        for (int j = 0; i + j < lim; ++j)
            t[i + j] += (unsigned long long)x.a[i] * y.a[j];
    ModInt z;
    z.a.resize(lim);
    for (int i = 0; i < lim; ++i) {
        t[i + 1] += t[i] / BASE;
        z.a[i] = t[i] % BASE;
    }
    z.a.back() %= lastBase;
    return z;
}
ModInt power(ModInt x, cpp_int e) {
    ModInt y = parseMod("1");
    while (e != 0) {
        if ((e.s.back() - '0') % 2)
            y = multiply(y, x);
        e = e / 2;
        if (e != 0)
            x = multiply(x, x);
    }
    return y;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s >> digits;
    cpp_int n = fromString(s);
    lim = (digits + 3) / 4;
    lastBase = 1;
    for (int i = 0; i < (digits - 1) % 4 + 1; ++i)
        lastBase *= 10;
    for (int p : {2, 5}) {
        cpp_int t = n;
        int v = 0;
        while (v < digits) {
            auto q = divmod(t, p);
            if (q.second != 0)
                break;
            t = q.first;
            ++v;
        }
        if (v > 0 && v < digits) {
            cout << -1 << '\n';
            return 0;
        }
    }
    ModInt x = parseMod(s);
    cpp_int period = pow10(digits - 1) * 4;
    for (int p : {2, 5})
        for (;;) {
            auto q = divmod(period, p);
            if (q.second != 0)
                break;
            auto v = multiply(power(x, q.first), x);
            if (v.a != x.a)
                break;
            period = q.first;
        }
    cout << period << '\n';
}