(luogu4884) 多少个 1?

发表于 分类于 ，

原题链接

思路:

纯数学题

\[ \begin{aligned} & 11 \cdots 1 \equiv K(mod\ m) \\ \Longrightarrow & 99 \cdots 9 \equiv 9K(mod\ m) \\ \Longrightarrow & 10^N \equiv 9K+1(mod\ m) \\ \end{aligned} \]

由于 \(m\) 是质数，所以逆推也成立.

使用 BSGS 求解即可. (代码中用的是 exBSGS 但是数据保证只需要用 BSGS 即可)

需要注意乘法的溢出问题.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <cmath>
#include <unordered_map>
using std::unordered_map;
#define int long long   //省事:)

int gcd(int a,int b) {
    return b==0 ? a : gcd(b,a%b);
}
int exgcd(int a,int b,int& x,int& y) {
    if(b == 0) {
        x = 1; y = 0;
        return a;
    }
    int g = exgcd(b,a%b,y,x);
    y -= a/b*x;
    return g;
}
int inv(int a,int m) {  //求逆
    int ret,y;
    exgcd(a,m,ret,y);
    return (ret+m)%m;
}

int exbsgs(int a,int p,int b) {
    if(b==1) {
        return 0;
    }
    int c = 1,g,k(0);
    while((g=gcd(a,p))!=1) {
        if(b%g!=0) {
            return -1;
        }
        c = (__int128)c*(a/g)%p;    //注意乘法溢出
        b /= g;
        p /= g;
        ++k;
        if(b == 1) {
            return k;
        }
    }
    b = (__int128)b*inv(c,p)%p;     //同上
    int m = ceil(sqrt(p));
    unordered_map<int,int> e;
    e[1] = 0;
    int x = a%p;
    for(int i(1);i<m;++i) {
        if(x==b) {
            return i+k;
        }
        if(!e.count(x)) {
            e[x] = i;
        }
        x = (__int128)x*a%p;
    }
    int anm = inv(x,p);
    x = ((__int128)b*anm)%p;
    for(int i(1);i<=m;++i) {
        if(e.count(x)) {
            return i*m + e[x] + k;
        }
        x = ((__int128)x*anm)%p;
    }
    return -1;
}

signed main() {
    int k,m;
    scanf("%lld %lld",&k,&m);
    k = (k*9+1)%m;
    int ans = exbsgs(10,m,k);
    printf("%lld",ans);
    return 0;
}