Skip to content

Commit f8c544c

Browse files
suisen-cpsuisen-cp
committed
ModInt
1 parent 6c272a4 commit f8c544c

2 files changed

Lines changed: 473 additions & 0 deletions

File tree

‎ModInt/ModInt.java‎

Lines changed: 339 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,339 @@
1+
class ModIntFactory {
2+
private final ModArithmetic ma;
3+
private final int mod;
4+
5+
public ModIntFactory(int mod) {
6+
this.ma = ModArithmetic.of(mod);
7+
this.mod = mod;
8+
}
9+
10+
public ModInt create(long value) {
11+
if ((value %= mod) < 0) value += mod;
12+
if (ma instanceof ModArithmetic.ModArithmeticMontgomery) {
13+
return new ModInt(((ModArithmetic.ModArithmeticMontgomery) ma).generate(value));
14+
}
15+
return new ModInt((int) value);
16+
}
17+
18+
class ModInt {
19+
private int value;
20+
private ModInt(int value) {
21+
this.value = value;
22+
}
23+
public int mod() {
24+
return mod;
25+
}
26+
public ModInt add(ModInt mi) {
27+
return new ModInt(ma.add(value, mi.value));
28+
}
29+
public ModInt sub(ModInt mi) {
30+
return new ModInt(ma.sub(value, mi.value));
31+
}
32+
public ModInt mul(ModInt mi) {
33+
return new ModInt(ma.mul(value, mi.value));
34+
}
35+
public ModInt div(ModInt mi) {
36+
return new ModInt(ma.div(value, mi.value));
37+
}
38+
public ModInt inv() {
39+
return new ModInt(ma.inv(value));
40+
}
41+
public ModInt pow(long b) {
42+
return new ModInt(ma.pow(value, b));
43+
}
44+
public int value() {
45+
if (ma instanceof ModArithmetic.ModArithmeticMontgomery) {
46+
return ((ModArithmetic.ModArithmeticMontgomery) ma).reduce(value);
47+
}
48+
return value;
49+
}
50+
@Override
51+
public String toString() {
52+
return String.valueOf(value());
53+
}
54+
@Override
55+
public boolean equals(Object o) {
56+
if (o instanceof ModInt) {
57+
ModInt mi = (ModInt) o;
58+
return mod() == mi.mod() && value() == mi.value();
59+
}
60+
return false;
61+
}
62+
@Override
63+
public int hashCode() {
64+
return (1 * 37 + mod()) * 37 + value();
65+
}
66+
}
67+
68+
private interface ModArithmetic {
69+
public int mod();
70+
public int add(int a, int b);
71+
public int sub(int a, int b);
72+
public int mul(int a, int b);
73+
public default int div(int a, int b) {
74+
return mul(a, inv(b));
75+
}
76+
public int inv(int a);
77+
public int pow(int a, long b);
78+
79+
public static ModArithmetic of(int mod) {
80+
if (mod <= 0) {
81+
throw new IllegalArgumentException();
82+
} else if (mod == 1) {
83+
return new ModArithmetic1();
84+
} else if (mod == 2) {
85+
return new ModArithmetic2();
86+
} else if (mod == 998244353) {
87+
return new ModArithmetic998244353();
88+
} else if (mod == 1000000007) {
89+
return new ModArithmetic1000000007();
90+
} else if ((mod & 1) == 1) {
91+
return new ModArithmeticMontgomery(mod);
92+
} else {
93+
return new ModArithmeticBarrett(mod);
94+
}
95+
}
96+
97+
static final class ModArithmetic1 implements ModArithmetic {
98+
public int mod() {return 1;}
99+
public int add(int a, int b) {return 0;}
100+
public int sub(int a, int b) {return 0;}
101+
public int mul(int a, int b) {return 0;}
102+
public int inv(int a) {throw new ArithmeticException("divide by zero");}
103+
public int pow(int a, long b) {return 0;}
104+
}
105+
static final class ModArithmetic2 implements ModArithmetic {
106+
public int mod() {return 2;}
107+
public int add(int a, int b) {return a ^ b;}
108+
public int sub(int a, int b) {return a ^ b;}
109+
public int mul(int a, int b) {return a & b;}
110+
public int inv(int a) {
111+
if (a == 0) throw new ArithmeticException("divide by zero");
112+
return a;
113+
}
114+
public int pow(int a, long b) {
115+
if (b == 0) return 1;
116+
return a;
117+
}
118+
}
119+
static final class ModArithmetic998244353 implements ModArithmetic {
120+
private final int mod = 998244353;
121+
public int mod() {
122+
return mod;
123+
}
124+
public int add(int a, int b) {
125+
int res = a + b;
126+
return res >= mod ? res - mod : res;
127+
}
128+
public int sub(int a, int b) {
129+
int res = a - b;
130+
return res < 0 ? res + mod : res;
131+
}
132+
public int mul(int a, int b) {
133+
return (int) (((long) a * b) % mod);
134+
}
135+
public int inv(int a) {
136+
int b = mod;
137+
long u = 1, v = 0;
138+
while (b >= 1) {
139+
long t = a / b;
140+
a -= t * b;
141+
int tmp1 = a; a = b; b = tmp1;
142+
u -= t * v;
143+
long tmp2 = u; u = v; v = tmp2;
144+
}
145+
u %= mod;
146+
if (a != 1) {
147+
throw new ArithmeticException("divide by zero");
148+
}
149+
return (int) (u < 0 ? u + mod : u);
150+
}
151+
public int pow(int a, long b) {
152+
if (b < 0) throw new ArithmeticException("negative power");
153+
long res = 1;
154+
long pow2 = a, idx = 1;
155+
while (b > 0) {
156+
long lsb = b & -b;
157+
for (; lsb != idx; idx <<= 1) {
158+
pow2 = (pow2 * pow2) % mod;
159+
}
160+
res = (res * pow2) % mod;
161+
b ^= lsb;
162+
}
163+
return (int) res;
164+
}
165+
}
166+
static final class ModArithmetic1000000007 implements ModArithmetic {
167+
private final int mod = 1000000007;
168+
public int mod() {
169+
return mod;
170+
}
171+
public int add(int a, int b) {
172+
int res = a + b;
173+
return res >= mod ? res - mod : res;
174+
}
175+
public int sub(int a, int b) {
176+
int res = a - b;
177+
return res < 0 ? res + mod : res;
178+
}
179+
public int mul(int a, int b) {
180+
return (int) (((long) a * b) % mod);
181+
}
182+
public int div(int a, int b) {
183+
return mul(a, inv(b));
184+
}
185+
public int inv(int a) {
186+
int b = mod;
187+
long u = 1, v = 0;
188+
while (b >= 1) {
189+
long t = a / b;
190+
a -= t * b;
191+
int tmp1 = a; a = b; b = tmp1;
192+
u -= t * v;
193+
long tmp2 = u; u = v; v = tmp2;
194+
}
195+
u %= mod;
196+
if (a != 1) {
197+
throw new ArithmeticException("divide by zero");
198+
}
199+
return (int) (u < 0 ? u + mod : u);
200+
}
201+
public int pow(int a, long b) {
202+
if (b < 0) throw new ArithmeticException("negative power");
203+
long res = 1;
204+
long pow2 = a, idx = 1;
205+
while (b > 0) {
206+
long lsb = b & -b;
207+
for (; lsb != idx; idx <<= 1) {
208+
pow2 = (pow2 * pow2) % mod;
209+
}
210+
res = (res * pow2) % mod;
211+
b ^= lsb;
212+
}
213+
return (int) res;
214+
}
215+
}
216+
static final class ModArithmeticMontgomery extends ModArithmeticDynamic {
217+
private final long negInv;
218+
private final long r2, r3;
219+
220+
private ModArithmeticMontgomery(int mod) {
221+
super(mod);
222+
long inv = 0;
223+
long s = 1, t = 0;
224+
for (int i = 0; i < 32; i++) {
225+
if ((t & 1) == 0) {
226+
t += mod;
227+
inv += s;
228+
}
229+
t >>= 1;
230+
s <<= 1;
231+
}
232+
long r = (1l << 32) % mod;
233+
this.negInv = inv;
234+
this.r2 = (r * r) % mod;
235+
this.r3 = (r2 * r) % mod;
236+
}
237+
private int generate(long x) {
238+
return reduce(x * r2);
239+
}
240+
private int reduce(long x) {
241+
x = (x + ((x * negInv) & 0xffff_ffffl) * mod) >>> 32;
242+
return (int) (x < mod ? x : x - mod);
243+
}
244+
@Override
245+
public int mul(int a, int b) {
246+
return reduce((long) a * b);
247+
}
248+
@Override
249+
public int inv(int a) {
250+
a = super.inv(a);
251+
return reduce(a * r3);
252+
}
253+
@Override
254+
public int pow(int a, long b) {
255+
return generate(super.pow(a, b));
256+
}
257+
}
258+
static final class ModArithmeticBarrett extends ModArithmeticDynamic {
259+
private static final long mask = 0xffff_ffffl;
260+
private final long mh;
261+
private final long ml;
262+
private ModArithmeticBarrett(int mod) {
263+
super(mod);
264+
/**
265+
* m = floor(2^64/mod)
266+
* 2^64 = p*mod + q, 2^32 = a*mod + b
267+
* => (a*mod + b)^2 = p*mod + q
268+
* => p = mod*a^2 + 2ab + floor(b^2/mod)
269+
*/
270+
long a = (1l << 32) / mod;
271+
long b = (1l << 32) % mod;
272+
long m = a * a * mod + 2 * a * b + (b * b) / mod;
273+
mh = m >>> 32;
274+
ml = m & mask;
275+
}
276+
private int reduce(long x) {
277+
long z = (x & mask) * ml;
278+
z = (x & mask) * mh + (x >>> 32) * ml + (z >>> 32);
279+
z = (x >>> 32) * mh + (z >>> 32);
280+
x -= z * mod;
281+
return (int) (x < mod ? x : x - mod);
282+
}
283+
@Override
284+
public int mul(int a, int b) {
285+
return reduce((long) a * b);
286+
}
287+
}
288+
static class ModArithmeticDynamic implements ModArithmetic {
289+
final int mod;
290+
public ModArithmeticDynamic(int mod) {
291+
this.mod = mod;
292+
}
293+
public int mod() {
294+
return mod;
295+
}
296+
public int add(int a, int b) {
297+
int sum = a + b;
298+
return sum >= mod ? sum - mod : sum;
299+
}
300+
public int sub(int a, int b) {
301+
int sum = a - b;
302+
return sum < 0 ? sum + mod : sum;
303+
}
304+
public int mul(int a, int b) {
305+
return (int) (((long) a * b) % mod);
306+
}
307+
public int inv(int a) {
308+
int b = mod;
309+
long u = 1, v = 0;
310+
while (b >= 1) {
311+
long t = a / b;
312+
a -= t * b;
313+
int tmp1 = a; a = b; b = tmp1;
314+
u -= t * v;
315+
long tmp2 = u; u = v; v = tmp2;
316+
}
317+
u %= mod;
318+
if (a != 1) {
319+
throw new ArithmeticException("divide by zero");
320+
}
321+
return (int) (u < 0 ? u + mod : u);
322+
}
323+
public int pow(int a, long b) {
324+
if (b < 0) throw new ArithmeticException("negative power");
325+
int res = 1;
326+
int pow2 = a, idx = 1;
327+
while (b > 0) {
328+
long lsb = b & -b;
329+
for (; lsb != idx; idx <<= 1) {
330+
pow2 = mul(pow2, pow2);
331+
}
332+
res = mul(res, pow2);
333+
b ^= lsb;
334+
}
335+
return res;
336+
}
337+
}
338+
}
339+
}

0 commit comments

Comments
 (0)