您的位置: 首页 > IT文章 > [POJ 2417]Discrete Logging

[POJ 2417]Discrete Logging

分类: IT文章 • 2024-02-16 19:46:18

Description

Given a prime P, 2 <= P < 2³¹, an integer B, 2 <= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that

    B^L == N (mod P)

Input

Read several lines of input, each containing P,B,N separated by a space.

Output

For each line print the logarithm on a separate line. If there are several, print the smallest; if there is none, print "no solution".

Sample Input

5 2 1
5 2 2
5 2 3
5 2 4
5 3 1
5 3 2
5 3 3
5 3 4
5 4 1
5 4 2
5 4 3
5 4 4
12345701 2 1111111
1111111121 65537 1111111111

Sample Output

0
1
3
2
0
3
1
2
0
no solution
no solution
1
9584351
462803587

Hint

The solution to this problem requires a well known result in number theory that is probably expected of you for Putnam but not ACM competitions. It is Fermat's theorem that states

   B^(P-1) == 1 (mod P)

for any prime P and some other (fairly rare) numbers known as base-B pseudoprimes. A rarer subset of the base-B pseudoprimes, known as Carmichael numbers, are pseudoprimes for every base between 2 and P-1. A corollary to Fermat's theorem is that for any m

   B^(-m) == B^(P-1-m) (mod P) .

题解

[POJ 2417]Discrete Logging

 1 //It is made by Awson on 2018.1.15
 2 #include <set>
 3 #include <map>
 4 #include <cmath>
 5 #include <ctime>
 6 #include <queue>
 7 #include <stack>
 8 #include <cstdio>
 9 #include <string>
10 #include <vector>
11 #include <cstdlib>
12 #include <cstring>
13 #include <iostream>
14 #include <algorithm>
15 #define LL long long
16 #define Abs(a) ((a) < 0 ? (-(a)) : (a))
17 #define Max(a, b) ((a) > (b) ? (a) : (b))
18 #define Min(a, b) ((a) < (b) ? (a) : (b))
19 #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
20 using namespace std;
21 const LL MOD = 233333;
22 void read(LL &x) {
23     char ch; bool flag = 0;
24     for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());
25     for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());
26     x *= 1-2*flag;
27 }
28 void write(LL x) {
29     if (x > 9) write(x/10);
30     putchar(x%10+48);
31 }
32 
33 LL a, b, c, ans;
34 struct MAP {
35     LL ha[MOD+5]; int id[MOD+5];
36     void clear() {for (int i = 0; i < MOD; i++) ha[i] = id[i] = -1; }
37     int count(LL x) {
38     LL pos = x%MOD;
39     while (true) {
40         if (ha[pos] == -1) return 0;
41         if (ha[pos] == x) return 1;
42         ++pos; if (pos >= MOD) pos -= MOD;
43     }
44     }
45     void insert(LL x, int idex) {
46     LL pos = x%MOD;
47     while (true) {
48         if (ha[pos] == -1 || ha[pos] == x) {ha[pos] = x, id[pos] = idex; return; }
49         ++pos; if (pos >= MOD) pos -= MOD;
50     }
51     }
52     int query(LL x) {
53     LL pos = x%MOD;
54     while (true) {
55         if (ha[pos] == x) return id[pos];
56         ++pos; if (pos >= MOD) pos -= MOD;
57     }
58     }
59 }mp;
60 
61 LL quick_pow(LL a, LL b, LL c) {
62     LL ans = 1;
63     while (b) {
64     if (b&1) ans = ans*a%c;
65     a = a*a%c, b >>= 1;
66     }
67     return ans;
68 }
69 LL BSGS(LL a, LL b, LL c) {
70     mp.clear();
71     LL tim = ceil(sqrt(c)), tmp = b%c;
72     for (int i = 0; i <= tim; i++) {
73     mp.insert(tmp, i); tmp = tmp*a%c;
74     }
75     LL t = tmp = quick_pow(a, tim, c);
76     for (int i = 1; i <= tim; i++) {
77     if (mp.count(tmp)) return tim*i-mp.query(tmp);
78     tmp = tmp*t%c;
79     }
80     return -1;
81 }
82 void work() {
83     while (~scanf("%lld%lld%lld", &c, &a, &b))
84     if ((ans = BSGS(a, b, c)) == -1) printf("no solution
");
85     else write(ans), putchar('
');
86 }
87 int main() {
88     work();
89     return 0;
90 }