这个是求扩展离散对数问题。_XY mod Z = K,给出X,Z,K,求Y。
_当Z是素数的时候直接用baby-step算法即可了。但是,模数不是素数的情况怎么办了。
方程a^X = b % c,可以进行一系列的转化。假设d = gcd(a,c),由a^(x-1) a = b % c,知道a^(x-1)要存在必须满足gcd(a,c) | b,如果满足这个条件,那么我们可以在方程2边同时除以d,方程是不变的。因为a^x = b + k c,再除以公约数d,得到方程a^(x-1) a / d = b / d + k c / d。根据以上推论,我们可以不断的除以d,直到gcd(a,c)=1。
假设我们除了k次,那么方程转化为a^(x-k) a^k/d^k = b / d^k + k c / d^k。令d = a^k/d^k,b’ = b / d^k,c’ = c / d^k,x’ = x - k,方程转化为a^x’ d = b’ % c’,得到a^x’ = b’ d^-1 % c’。
现在直接用baby-step解方程a^x’ = b’ * (d^-1) % c’即可。注意到x=x’+k,如果存在x小于k的解,那么x’小于0,但是由baby-step是不会求负的次数的,所以需要先枚举一下是否存在小于k的解,由于输入的数据不会超过10^9的,假设k不超过50进行枚举即可了。

代码如下:

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long INT;
#define MAX (1000000)
INT nData[MAX];
INT nKey[MAX];

INT HashPos(INT key)
{
return ((unsigned)(key ^ 0xA5A5A5A5)) % MAX;
}

void HashAdd(INT key, INT data)
{
INT nPos = HashPos(key);
while (nData[nPos] != -1)
{
nPos = (nPos + 1) % MAX;
}
nData[nPos] = data;
nKey[nPos] = key;
}

INT HashQuery(INT key)
{
INT nPos = HashPos(key);
while (nData[nPos] != -1)
{
if (nKey[nPos] == key)
{
return nData[nPos];
}
nPos = (nPos + 1) % MAX;
}

return -1;
}

INT MultMod(INT nA, INT nB, INT nC)
{
INT nAns = 0;
while (nB)
{
if (nB 1)
{
nAns = (nAns + nA) % nC;
}
nA = (2 * nA) % nC;
nB >>= 1;
}
return nAns;
}

INT PowerMod(INT nA, INT nX, INT nC)
{
INT nAns = 1;
nA %= nC;
while (nX)
{
if (nX 1)
{
nAns = MultMod(nAns, nA, nC);
}
nA = MultMod(nA, nA, nC);
nX >>= 1;
}
return nAns;
}

INT gcd(INT nA, INT nB)
{
if (nA < nB)swap(nA, nB);
while (nB)
{
INT nT = nA;
nA = nB;
nB = nT % nB;
}
return nA;
}
//d = nA * nX + nB * nY(nA > nB, nA是模数)
INT egcd(INT nA, INT nB, INT nX, INT nY)
{
if (nA < nB)swap(nA, nB);
if (nB == 0)
{
nX = 1;
nY = 0;
return nA;
}
INT nRet = egcd(nB, nA % nB, nX, nY);
INT nT = nX;
nX = nY;
nY = nT - (nA / nB) * nY;
return nRet;
}

INT GetAns(INT nA, INT nB, INT nC)
{
if (nC == 0)return -1;
//先枚举0-50,扩展baby-step的过程可能会漏掉这些解
INT nTemp = 1;
nB %= nC;
for (INT i = 0; i <= 50; ++i)
{
if (nTemp == nB)
{
return i;
}
nTemp = MultMod(nTemp, nA, nC);
}

//如果nC不是素数,那么方程nA^x = nB + k*nC
//可以不到除以gcd(nC,nA)
//如果gcd(nC,nA)|nB不成立,方程无解,
//这个由a*x=b%c有解必须满足gcd(a,c)|b一样
INT d;
INT nD = 1;//nD最后是A^k次,k是nC中因子d的次数
INT k = 0;
while ((d = gcd(nC, nA)) != 1)
{
k++;
nC /= d;
if (nB % d)return -1;
nB /= d;
nD = MultMod(nD, nA / d, nC);
}
//现在方程转化为nA^(x-k) * nA^k/d^k = nB/d^k % nC/d^k
//其实就是方程2侧除以d^k次而已,这样的做法与原方程是等价的
//令nD = nA^k/d^k,则nA^x'*nD = nB' % nC',
//解该方程,那么x=x'+k
//注意,如果x<k,那么x'为负数,baby-step无法求出,故在函数开头进行枚举
memset(nKey, -1, sizeof(nKey));
memset(nData, -1, sizeof(nData));
INT nM = ceil(sqrt(1.0 * nC));
nTemp = 1;
for (INT j = 0; j <= nM; ++j)
{
HashAdd(nTemp, j);
nTemp = MultMod(nTemp, nA, nC);
}
INT nK = PowerMod(nA, nM, nC);
for (int i = 0; i <= nM; ++i)
{
INT x, y;
egcd(nC, nD, x, y);//y = nD^-1,nD = nD*(nA^m)^i
y = (y + nC) % nC;//这句话是必须的,y很可能就是负数
INT nR = MultMod(y, nB, nC);//nR=nB*nD^-1
int j = HashQuery(nR);
if (j != -1)
{
return nM * i + j + k;
}

nD = MultMod(nD, nK, nC);
}
return -1;
}

int main()
{
INT nA, nB, nC;

while (scanf("%I64d%I64d%I64d", &nA, &nC, &nB), nA + nB + nC)
{
INT nAns = GetAns(nA, nB, nC);
if (nAns == -1)
{
printf("No Solution\n");
}
else
{
printf("%I64d\n", nAns);
}
}

return 0;
}


版权声明:

本作品采用知识共享署名 2.5 中国大陆许可协议进行许可,欢迎转载,但转载请注明来自远行’s Life,并保持转载后文章内容的完整。本人保留所有版权相关权利。

本文链接:http://xiaopengcheng.top/2012/08/05/poj 3243 Clever Y 扩展离散对数/