Problem Statement
You are given four positive integers a,b,c and m. Let x = bc. Calculate and return the following value: (ax mod m).
Definition
- Class:
- SimpleMathProblem
- Method:
- calculate
- Parameters:
- int, int, int, int
- Returns:
- int
- Method signature:
- int calculate(int a, int b, int c, int m)
- (be sure your method is public)
Constraints
- a,b,c and m will each be between 1 and 737,373,737, inclusive.
Examples
1
1
1
737
Returns: 1
1^(1^1) modulo 737 is 1.
3
7
3
123456789
Returns: 63564408
First we get that x = 7^3 = 343. Then we compute the answer: (3^x modulo 123456789).
12
34
56
78
Returns: 66
3737373
7373737
37373
737373737
Returns: 214080347
1
1
1
2
Returns: 1
1
1
2
2
Returns: 1
1
2
1
2
Returns: 1
1
2
2
2
Returns: 1
1
3
1
2
Returns: 1
1
3
2
2
Returns: 1
2
1
1
4
Returns: 2
2
1
1
1
Returns: 0
2
1
2
4
Returns: 2
2
1
2
1
Returns: 0
2
2
1
8
Returns: 4
2
2
1
2
Returns: 0
2
2
2
32
Returns: 16
2
2
2
8
Returns: 0
2
3
1
16
Returns: 8
2
3
1
4
Returns: 0
2
3
2
1024
Returns: 512
2
3
2
256
Returns: 0
3
1
1
6
Returns: 3
3
1
1
1
Returns: 0
3
1
2
6
Returns: 3
3
1
2
1
Returns: 0
3
2
1
18
Returns: 9
3
2
1
3
Returns: 0
3
2
2
162
Returns: 81
3
2
2
27
Returns: 0
3
3
1
54
Returns: 27
3
3
1
9
Returns: 0
3
3
2
39366
Returns: 19683
3
3
2
6561
Returns: 0
4
3
2
131072
Returns: 0
4
3
2
262144
Returns: 0
4
3
2
524288
Returns: 262144
737373737
737373737
737373737
737373737
Returns: 0
737373737
737373737
737373737
737373731
Returns: 224569275
737373737
737373737
737373737
181119236
Returns: 169635145
1
737373737
737373737
98802491
Returns: 1
1
308278125
582670712
314160782
Returns: 1
737373737
1
737373737
203553290
Returns: 126713867
12979925
1
311274077
123970461
Returns: 12979925
309015862
1
376622406
88309203
Returns: 44088253
206822987
680725908
1
224972348
Returns: 163786781
150933586
411586059
678105573
150933586
Returns: 0
646584830
65089976
209907606
65089976
Returns: 49185336
523618772
676131385
522877180
522877180
Returns: 65480532
262948113
381040812
381040812
381040812
Returns: 252805401
513245845
109897200
418967832
385445802
Returns: 55063687
449677069
635493771
29933568
425421270
Returns: 101859679
582352381
328612129
490361885
466985983
Returns: 59605062
240876894
613516074
350178075
576657021
Returns: 302794827
589819340
108815762
213935499
253554401
Returns: 11169221
200630267
375806085
68119788
487831030
Returns: 288868307
140738810
85770777
206174059
6671800
Returns: 4831800
2
10
10
1024
Returns: 0
2^(10^10) is divisible by 1024, hence the remainder is zero.
47
53
912
1
Returns: 0
Any integer modulo 1 is zero.
999
33
121213
100000000
Returns: 83712999
567
1000000
500000000
23224
Returns: 5993
700000000
700000000
700000000
699999999
Returns: 1
99999999
33333333
12121399
100000000
Returns: 99999999
12381232
12312242
12313131
41
Returns: 16
3737373
77373737
77737373
737373737
Returns: 597790725
3
1
1
9
Returns: 3
568
1000000
500000000
23224
Returns: 17912
3
6
1
9
Returns: 0
2
2
2
4
Returns: 0
12381232
12312242
12313131
412384
Returns: 124896
666666
777777
888888
123456
Returns: 55296
16
666666
777777
24
Returns: 16