题解 P4884 【多少个1？】

· · 题解

完全不知道为什么此题必须用__int128Windows下不能用。快速乘+map完全可通过本题。

然而快速幂是多余的

知道a^i可以推出a^{i+1}，知道(a^p)^i可以推出(a^p)^{i+1}，这是常识。这样就愉快地变成O(\sqrt{p}log\sqrt{p})了，复杂度极其正确（然而快速幂再多一个log）。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll times(ll a, ll b, ll m) {
    ll ans = 0;
    while (b) {
        if (b & 1) ans = (ans + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return ans;
}
ll bsgs(ll a, ll b, ll m) {
    map<ll, int> mp;
    int p = ceil(sqrt(m));
    ll num = 1;
    mp[1] = 0;
    for (int i = 1; i <= p; i++) num = times(num, a, m), mp[times(num, b, m)] = i;
    ll n = 1;
    for (int i = 1; i <= p; i++) {
        n = times(n, num, m);
        if (mp.find(n) != mp.end()) return 1ll * p * i - mp[n];
    }
    return -1;
}
int main() {
    ll k, m;
    cin >> k >> m;
    cout << bsgs(10, 9 * k + 1, m) << endl;
    return 0;
}