Chaos Slover 补档计划 - 指标与原根

2015.12.10 19:59 Thu| 8 visits oi_2016| ChaosSlover补档计划| Text

BZOJ2242 [SDOI2011]计算器

更新了一下模板,变得更好写了 233。

昨天鼓捣了一下编辑器的配色,和色的感觉还不错(然而为何那么像浅色版的 monokai..)。

 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
#include <bits/stdc++.h>
using namespace std;

pair<int, int> exgcd(int a, int b)
{
    if (b == 0) return make_pair(1, 0);
    pair<int, int> t = exgcd(b, a % b);
    return make_pair(t.second, t.first - a / b * t.second);
}

int power(int a, int b, int p)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = 1ll * re * a % p;
        a = 1ll * a * a % p; b >>= 1;
    }
    return re;
}

int bsgs(int a, int b, int p)
{
    map<int, int> m;
    if (!(a %= p)) return b ? -1 : 1;
    int blo = ceil(sqrt(double(p)));
    for (int i = 0, t = 1; i < blo; ++i)
    {
        if (m.find(t) == m.end())
            m[t] = i;
        t = 1ll * t * a % p;
    }
    int inv = power(a, p - blo - 1, p);
    for (int i = 0; i < blo; ++i)
    {
        if (m.find(b) != m.end())
            return i * blo + m[b];
        b = 1ll * b * inv % p;
    }
    return -1;
}

int t, k, a, b, p;

int main()
{
    cin >> t >> k;
    for (int i = 1; i <= t; ++i)
    {
        cin >> a >> b >> p;
        if (k == 1)
        {
            printf("%d\n", power(a, b, p));
        }
        if (k == 2)
        {
            int d = __gcd(a, p);
            if (b % d) puts("Orz, I cannot find x!");
            else printf("%d\n", (1ll * exgcd(a, p).first * b / d % p + p) % p);
        }
        if (k == 3)
        {
            int t = bsgs(a, b, p);
            if (t == -1) puts("Orz, I cannot find x!");
            else printf("%d\n", t);
        }
    }
}

BZOJ1467&2480 Pku3243 clever Y

拓展 BSGS 算法。首先需要枚举 log P 以内的答案,保证答案的正确性。

 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
#include <bits/stdc++.h>
using namespace std;

pair<int, int> exgcd(int a, int b)
{
    if (b == 0) return make_pair(1, 0);
    pair<int, int> t = exgcd(b, a % b);
    return make_pair(t.second, t.first - a / b * t.second);
}

int power(int a, int b, int p)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = 1ll * re * a % p;
        a = 1ll * a * a % p; b >>= 1;
    }
    return re;
}

int exbsgs(int a, int b, int p)
{
    if (!(a %= p)) return b ? -1 : 1;
    for (int i = 0, t = 1; i < 32; ++i)
    {
        if (t == b) return i;
        t = 1ll * t * a % p;
    }
    int d = 1, t = 0, cnt = 0;
    while ((t = __gcd(a, p)) != 1)
    {
        if (b % t) return -1;
        b /= t, p /= t;
        d = 1ll * d * a / t % p, ++cnt;
    }
    map<int, int> m;
    int blo = ceil(sqrt(double(p)));
    for (int i = 0, t = 1; i < blo; ++i)
    {
        if (m.find(t) == m.end())
            m[t] = i;
        t = 1ll * t * a % p;
    }
    int inv = (exgcd(power(a, blo, p), p).first % p + p) % p;
    d = (exgcd(d, p).first % p + p) % p;
    for (int i = 0; i < blo; ++i)
    {
        if (m.find(1ll * d * b % p) != m.end())
            return i * blo + m[1ll * d * b % p] + cnt;
        d = 1ll * d * inv % p;
    }
    return -1;
}

int a, b, p;

int main()
{
    while (cin >> a >> p >> b, p)
    {
        int t = exbsgs(a, b, p);
        if (t == -1) puts("No Solution");
        else cout << t << endl;
    }
    return 0;
}

BZOJ1319&1420 Sgu261Discrete Roots

设 G 是 C 的原根,那么可以将原式 $x^A\equiv B\pmod C$ 化简为 $A*\text{ind} x \equiv \text{ind} B \pmod {\varphi (C)}$。

用 BSGS 求出 $\text{ind}B$ ,之后用拓展 GCD 求出所有的 $\text{ind}x$,在用原根求一下快速幂就是解了。

注意上一步再求 exgcd 的时候,如果 A 没有逆元,那么就把 A、B、φ(P) 在一起约分一下吧。如果 B 不能整除 A 和 φ(P) 的最大公约数,那么无解。

 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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;

int power(int a, int b, int p)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = 1ll * re * a % p;
        a = 1ll * a * a % p; b >>= 1;
    }
    return re;
}

pair<int, int> exgcd(int a, int b)
{
    if (b == 0) return make_pair(1, 0);
    pair<int, int> t = exgcd(b, a % b);
    return make_pair(t.second, t.first - a / b * t.second);
}

bool check(int p, int g)
{
    int t = p - 1;
    for (int i = 2; i * i <= p; ++i)
    {
        if (t % i == 0 && power(g, (p - 1) / i, p) == 1) return false;
        while (t % i == 0) t /= i;
    }
    if (t != 1 && power(g, (p - 1) / t, p) == 1) return false;
    return true;
}

int getroot(int p)
{
    for (int i = 2; i < p; ++i)
        if (check(p, i)) return i;
    return 0;
}

int getphi(int n)
{
    int re = n;
    for (int i = 2; i * i <= n; ++i)
    {
        if (n % i == 0) re = re / i * (i - 1);
        while (n % i == 0) n /= i;
    }
    if (n != 1) re = re / n * (n - 1);
    return re;
}

int bsgs(int a, int b, int p)
{
    map<int, int> m;
    if (!(a %= p)) return b ? -1 : 1;
    int blo = ceil(sqrt(double(p)));
    for (int i = 0, t = 1; i < blo; ++i)
    {
        if (m.find(t) == m.end()) m[t] = i;
        t = 1ll * t * a % p;
    }
    int inv = power(a, p - blo - 1, p);
    for (int i = 0; i < blo; ++i)
    {
        if (m.find(b) != m.end())
            return i * blo + m[b];
        b = 1ll * b * inv % p;
    }
    return -1;
}

int p, a, b;
vector<int> v;

int main()
{
    cin >> p >> a >> b;
    if (b == 0) { puts("1\n0\n"); return 0; }
    int g = getroot(p), q = getphi(p);
    int indb = bsgs(g, b, p);
    int gcd = __gcd(a, q);
    if (indb % gcd) { puts("0"); return 0; }
    int t = q / gcd;
    int c = (exgcd(a / gcd, t).first % t + t) % t;
    c = 1ll * c * indb / gcd % t;
    while (c <= q)
        v.push_back(power(g, c, p)), c += t;
    cout << v.size() << endl;
    sort(v.begin(), v.end());
    for (int i = 0; i < (int)v.size(); ++i)
        printf("%d\n", v[i]);
    return 0;
}

BZOJ4128 Matrix

仍然是 BSGS,只不过数字变成了矩阵,所以关键的问题就是如何求矩阵的逆。

新建一个 n*n 的单位矩阵,在对原矩阵进行初等矩阵变换的同时,对这个单位矩阵进行相同的变换。如果我们将原矩阵消成了单位矩阵,那么这个新矩阵就是原矩阵的逆啦!(听起来好像挺简单的)

  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
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <bits/stdc++.h>
using namespace std;

#define N 70

int n, p;

long long power(long long a, long long b, long long p)
{
    long long re = 1;
    while (b)
    {
        if (b & 1) re = re * a % p;
        a = a * a % p; b >>= 1;
    }
    return re;
}

struct matrix
{
    long long t[N][N];

    matrix() { memset(t, 0, sizeof t); }

    matrix(bool flag)
    {
        memset(t, 0, sizeof t);
        for (int i = 0; i < n; ++i)
            t[i][i] = 1;
    }

    long long hash()
    {
        static long long mod = 23333333333333333ll;
        long long re = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                re = re * 131 + t[i][j] % mod;
        return re;
    }

    friend matrix inverse(matrix m)
    {
        matrix re(true);
        for (int i = 0; i < n; ++i)
        {
            int t = -1;
            for (int j = i; j < n; ++j)
                if (m.t[j][i]) { t = j; break; }
            if (t == -1) { puts("error"); return re; }
            for (int j = 0; j < n; ++j)
                swap(m.t[i][j], m.t[t][j]),
                swap(re.t[i][j], re.t[t][j]);
            int inv = power(m.t[i][i], p - 2, p);
            for (int j = 0; j < n; ++j)
                m.t[i][j] = m.t[i][j] * inv % p,
                re.t[i][j] = re.t[i][j] * inv % p;
            for (int j = 0; j < n; ++j)
                if (j != i)
                {
                    int temp = (p - m.t[j][i]) % p;
                    for (int k = 0; k < n; ++k)
                        m.t[j][k] = (m.t[j][k] + temp * m.t[i][k]) % p,
                        re.t[j][k] = (re.t[j][k] + temp * re.t[i][k]) % p;
                }
        }
        return re;
    }

    friend matrix operator *(const matrix &a, const matrix &b)
    {
        matrix re;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                for (int k = 0; k < n; ++k)
                    re.t[i][j] = (re.t[i][j] + a.t[i][k] * b.t[k][j]) % p;
        return re;
    }

    matrix &operator *=(const matrix &x) { return *this = *this * x; }

    friend matrix pow(matrix m, int t)
    {
        matrix re;
        for (int i = 0; i < n; ++i)
            re.t[i][i] = 1;
        while (t)
        {
            if (t & 1) re *= m;
            t >>= 1; m *= m;
        }
        return re;
    }

    friend ostream &operator <<(ostream &out, const matrix &x)
    {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                out << x.t[i][j] << " \n"[j == n - 1];
        return out;
    }
};

int bsgs(matrix a, matrix b)
{
    map<long long, int> m;
    int blo = ceil(sqrt(double(p)));
    matrix t(true); long long h = 0;
    for (int i = 0; i < blo; ++i)
    {
        if (m.find(h = t.hash()) == m.end()) m[h] = i;
        t *= a;
    }
    matrix inv = inverse(pow(a, blo));
    for (int i = 0; i < blo; ++i)
    {
        if (m.find(h = b.hash()) != m.end())
            return i * blo + m[h];
        b *= inv;
    }
    return -1;
}

matrix a, b;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n >> p;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            a.t[i][j] = read();
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            b.t[i][j] = read();
    cout << bsgs(a, b) << endl;
    return 0;
}