OI

AHSDFZ 20170303 Number Theory (theory.pas/c/cpp)

Description

给出x,m,p 求一个合法的n满足： \( n^{2n} + n^m \equiv x \pmod p \) ，p为质数。 本题special judge

Input

x, m, p

Output

一个合法n（大小无限制，保证有解）

Sample Input

17 0 997

Sample Output

2

HINT

\( p \le 10^9 + 7, x \le p, m \le p \)

Solution

我们假设g为mod P意义下的原根。

我们不妨假设 \( n \equiv g \pmod p \) ，那么我们有 \( n^{2n} \equiv x – g^m \pmod p \) 不妨让 \( g^k \equiv x – g^m \pmod p \) 则 \( 2n \equiv k \pmod p-1 \) 且 \( n \equiv g \)。

然后对于这两个套用中国剩余定理，然后判断下n合不合法即可。

Source

 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

#include <map>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
int tot;
map<LL, LL> M;
LL dst[123456], x, m, p;
LL ksc(LL a, LL b, LL c) {
    LL r = 0, t = a;
    while (b) {
        if (b & 1) r = (r + t) % c;
        t = (t + t) % c;
        b >>= 1;
    }
    return r;
}
LL ksm(LL a, LL b, LL c) {
    LL r = 1, t = a;
    while (b) {
        if (b & 1) r = ksc(r,t,c);
        t=ksc(t,t,c);
        b >>= 1;
    }
    return r;
}
void fen(LL x) {
    for (LL i = 2; i * i <= x; ++i) {
        if (x % i == 0) {dst[tot++] = i; while (x % i == 0) x /= i;}
    }
    if (x > 1) dst[tot++] = x;
}
void exgcd(LL a, LL b, LL &x, LL &y) {
    if (b == 0) {
        x = 1; y = 0;
    } else {
        exgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }
}
bool check(LL x) {
    for (int i = 0; i < tot; ++i)
        if (ksm(x, (p - 1) / dst[i], p) == 1) return false;
    return true;
}
LL niyuan(LL a, LL b) {
    LL g = __gcd(a, b);
    a /= g; b /= g;
    LL x, y;
    exgcd(a, b, x, y);
    return (x % b + b) % b;
}
LL BSGS(LL a, LL b, LL p) {
    LL s = sqrt(p) + 0.5, h;
    LL val = 1, tmp = ksm(a, s, p), ret = ~0ull>>1;
    M.clear();
    for (LL i = 0; i <= s; ++i) {
        if (M.count(val) == 0) M[val] = i;
        val = (val * tmp) % p;
    }
    val = b; tmp = ksm(a, p - 2, p);
    for (LL i = 0; i <= s; ++i) {
        if (M.count(val) == 1) {
            h = i + M[val] * s;
            if (h != 0) ret = min(ret, h);
        }
        val = (val * tmp) % p;
    }
    return ret;
}
int main() {
    LL y, k, m1, a1, m2, a2, M, n;
    scanf("%lld %lld %lld", &x, &m, &p);
    x %= p; fen(p - 1);
    for (LL g = 2; g < p; ++g) {
        if (!check(g)) continue;
        y = (x - ksm(g, m, p) + p) % p;
        k = BSGS(g, y, p);
        m1 = p; a1 = g;
        m2 = p - 1; a2 = k / 2;
        M = m1 * m2;
        n = (ksc(ksc(a1, m2, M), niyuan(m2, m1), M) + ksc(ksc(a2, m1, M), niyuan(m1, m2), M)) % M;
        if ((ksm(n, n * 2, p) + ksm(n, m, p)) % p == x % p) {
            printf("%lld", n);
            return 0;
        }
    }
}