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
|
int exp_table[] = {1,2,4,8,16,32,64,27,54,7,14,28,56,11,22,44,88,75,49,98,95,89,77,53,5,10,20,40,80,59,17,34,68,35,70,39,78,55,9,18,36,72,43,86,71,41,82,63,25,50,100,99,97,93,85,69,37,74,47,94,87,73,45,90,79,57,13,26,52,3,6,12,24,48,96,91,81,61,21,42,84,67,33,66,31,62,23,46,92,83,65,29,58,15,30,60,19,38,76,51,0};
int log_table[] = {100,0,1,69,2,24,70,9,3,38,25,13,71,66,10,93,4,30,39,96,26,78,14,86,72,48,67,7,11,91,94,84,5,82,31,33,40,56,97,35,27,45,79,42,15,62,87,58,73,18,49,99,68,23,8,37,12,65,92,29,95,77,85,47,6,90,83,81,32,55,34,44,41,61,57,17,98,22,36,64,28,76,46,89,80,54,43,60,16,21,63,75,88,53,59,20,74,52,19,51,50};
int exp_table2[] = {0,2,4,8,16,32,64,27,54,7,14,28,56,11,22,44,88,75,49,98,95,89,77,53,5,10,20,40,80,59,17,34,68,35,70,39,78,55,9,18,36,72,43,86,71,41,82,63,25,50,100,99,97,93,85,69,37,74,47,94,87,73,45,90,79,57,13,26,52,3,6,12,24,48,96,91,81,61,21,42,84,67,33,66,31,62,23,46,92,83,65,29,58,15,30,60,19,38,76,51,1};
int log_table2[] = {0,100,1,69,2,24,70,9,3,38,25,13,71,66,10,93,4,30,39,96,26,78,14,86,72,48,67,7,11,91,94,84,5,82,31,33,40,56,97,35,27,45,79,42,15,62,87,58,73,18,49,99,68,23,8,37,12,65,92,29,95,77,85,47,6,90,83,81,32,55,34,44,41,61,57,17,98,22,36,64,28,76,46,89,80,54,43,60,16,21,63,75,88,53,59,20,74,52,19,51,50};
int p1 = 100;
int p = 101;
int zero = 100;
int minus_one = 50;
// aring-zzp.hpp
void subtract_multiple(int &result, int a, int b)
{
// we assume: a, b are NONZERO!!
// result -= a*b
int ab = a + b;
if (ab > p1) ab -= p1;
int n = exp_table[result] - exp_table[ab];
if (n < 0) n += p;
result = log_table[n];
}
// coeffrings.hpp
inline int modulus_add(int a, int b, int p)
{
int t = a + b;
return (t < p ? t : t - p);
}
inline int modulus_sub(int a, int b, int p)
{
int t = a - b;
return (t < 0 ? t + p : t);
}
void subtract(int &result, int a, int b)
{
if (b == zero)
result = a;
else if (a == zero)
result = modulus_add(b, minus_one, p1);
else
{
int n = modulus_sub(exp_table[a], exp_table[b], p);
result = log_table[n];
}
}
void subtract_multiple2(int &result, int a, int b)
{
// we assume: a, b are NONZERO!!
// result -= a*b
int ab = modulus_add(a, b, p1);
subtract(result, result, ab);
return;
}
|
