ACM_高次同余方程

复制代码/*poj 3243 *解决高次同余方程的应用，已知 X^Y = K mod Z, 及X,Z,K的值，求 Y 的值 */ #include<cstdio> #include<cstring> #include<cmath> using namespace std; #define lint __int64 #define MAXN 131071 struct HashNode { lint data, id, next; }; HashNode hash[MAXN<<1]; bool flag[MAXN<<1]; lint top; void Insert ( lint a, lint b ) { lint k = b & MAXN; if ( flag[k] == false ) { flag[k] = true; hash[k].next = -1; hash[k].id = a; hash[k].data = b; return; } while( hash[k].next != -1 ) { if( hash[k].data == b ) return; k = hash[k].next; } if ( hash[k].data == b ) return; hash[k].next = ++top; hash[top].next = -1; hash[top].id = a; hash[top].data = b; } lint Find ( lint b ) { lint k = b & MAXN; if( flag[k] == false ) return -1; while ( k != -1 ) { if( hash[k].data == b ) return hash[k].id; k = hash[k].next; } return -1; } lint gcd ( lint a, lint b ) { return b ? gcd ( b, a % b ) : a; } lint ext_gcd (lint a, lint b, lint& x, lint& y ) { lint t, ret; if ( b == 0 ) { x = 1, y = 0; return a; } ret = ext_gcd ( b, a % b, x, y ); t = x, x = y, y = t - a / b * y; return ret; } lint mod_exp ( lint a, lint b, lint n ) { lint ret = 1; a = a % n; while ( b >= 1 ) { if( b & 1 ) ret = ret * a % n; a = a * a % n; b >>= 1; } return ret; } lint BabyStep_GiantStep ( lint A, lint B, lint C ) { top = MAXN; B %= C; lint tmp = 1, i; for ( i = 0; i <= 100; tmp = tmp * A % C, i++ ) if ( tmp == B % C ) return i; lint D = 1, cnt = 0; while( (tmp = gcd(A,C)) !=1 ) { if( B % tmp ) return -1; C /= tmp; B /= tmp; D = D * A / tmp % C; cnt++; } lint M = (lint)ceil(sqrt(C+0.0)); for ( tmp = 1, i = 0; i <= M; tmp = tmp * A % C, i++ ) Insert ( i, tmp ); lint x, y, K = mod_exp( A, M, C ); for ( i = 0; i <= M; i++ ) { ext_gcd ( D, C, x, y ); // D * X = 1 ( mod C ) tmp = ((B * x) % C + C) % C; if( (y = Find(tmp)) != -1 ) return i * M + y + cnt; D = D * K % C; } return -1; } int main() { lint A, B, C; while( scanf("%I64d%I64d%I64d",&A,&C,&B ) !=EOF ) { if ( !A && !B && !C ) break; memset(flag,0,sizeof(flag)); lint tmp = BabyStep_GiantStep ( A, B, C ); if ( tmp == -1 )puts("No Solution"); else printf("%I64dn",tmp); } return 0; }

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
/*poj 3243 
 *解决高次同余方程的应用，已知 X^Y = K mod Z, 及X,Z,K的值，求 Y 的值 
*/

#include<cstdio>  
#include<cstring>  
#include<cmath>  
using namespace std;  
#define lint __int64  
#define MAXN 131071  
struct HashNode { lint data, id, next; };  
HashNode hash[MAXN<<1];  
bool flag[MAXN<<1];  
lint top;  
  
void Insert ( lint a, lint b )  
{  
    lint k = b & MAXN;  
    if ( flag[k] == false )  
    {  
        flag[k] = true;  
        hash[k].next = -1;  
        hash[k].id = a;  
        hash[k].data = b;  
        return;  
    }  
    while( hash[k].next != -1 )  
    {  
        if( hash[k].data == b ) return;  
        k = hash[k].next;  
    }  
    if ( hash[k].data == b ) return;  
    hash[k].next = ++top;  
    hash[top].next = -1;  
    hash[top].id = a;  
    hash[top].data = b;  
}  
  
lint Find ( lint b )  
{  
    lint k = b & MAXN;  
    if( flag[k] == false ) return -1;  
    while ( k != -1 )  
    {  
        if( hash[k].data == b ) return hash[k].id;  
        k = hash[k].next;  
    }  
    return -1;  
}  
  
lint gcd ( lint a, lint b )  
{  
    return b ? gcd ( b, a % b ) : a;  
}  
  
lint ext_gcd (lint a, lint b, lint& x, lint& y )  
{  
    lint t, ret;  
    if ( b == 0 )  
    {  
        x = 1, y = 0;  
        return a;  
    }  
    ret = ext_gcd ( b, a % b, x, y );  
    t = x, x = y, y = t - a / b * y;  
    return ret;  
}  
  
lint mod_exp ( lint a, lint b, lint n )  
{  
    lint ret = 1;  
    a = a % n;  
    while ( b >= 1 )  
    {  
        if( b & 1 )  
            ret = ret * a % n;  
        a = a * a % n;  
        b >>= 1;  
    }  
    return ret;  
}  
  
lint BabyStep_GiantStep ( lint A, lint B, lint C )  
{  
    top = MAXN;  B %= C;  
    lint tmp = 1, i;  
    for ( i = 0; i <= 100; tmp = tmp * A % C, i++ )  
        if ( tmp == B % C ) return i;  
  
    lint D = 1, cnt = 0;  
    while( (tmp = gcd(A,C)) !=1 )  
    {  
        if( B % tmp ) return -1;  
        C /= tmp;  
        B /= tmp;  
        D = D * A / tmp % C;  
        cnt++;  
    }  
  
    lint M = (lint)ceil(sqrt(C+0.0));  
    for ( tmp = 1, i = 0; i <= M; tmp = tmp * A % C, i++ )  
        Insert ( i, tmp );  
  
    lint x, y, K = mod_exp( A, M, C );  
    for ( i = 0; i <= M; i++ )  
    {  
        ext_gcd ( D, C, x, y ); // D * X = 1 ( mod C )  
        tmp = ((B * x) % C + C) % C;  
        if( (y = Find(tmp)) != -1 )  
            return i * M + y + cnt;  
        D = D * K % C;  
    }  
    return -1;  
}  
  
int main()  
{  
    lint A, B, C;  
    while( scanf("%I64d%I64d%I64d",&A,&C,&B ) !=EOF )  
    {  
        if ( !A && !B && !C ) break;  
        memset(flag,0,sizeof(flag));  
        lint tmp = BabyStep_GiantStep ( A, B, C );  
        if ( tmp == -1 )puts("No Solution");  
        else printf("%I64dn",tmp);  
    }  
    return 0;  
}