/home/toolbox/public_html/solutions/3/374/a.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9 #include <ctype.h>
10
11 #define TRUE (1 == 1)
12 #define FALSE (1 != 1)
13
14 #define DEBUG if (FALSE)
15
16 #define MAX_LINE 257
17
18 /*
19 * Author: Isaac Traxler
20 * Date: 2021-11-11
21 * Purpose: fun
22 * Problem: 374 - Big Mod
23 */
24
25 /*
26 * This template reads lines of data at a time until end of file.
27 */
28
29 /* this code derived from algorithm in Cormen algorithms book
30 * (Section on Raising to powers with repeated squaring)
31 * Section 31.6 of 2nd edition
32 */
33
34 long long b;
35 long long p;
36 long long m;
37
38 void init()
39 {
40 /* FUNCTION init */
41 } /* FUNCTION init */
42
43 void dump()
44 {
45 /* FUNCTION dump */
46 } /* FUNCTION dump */
47
48 int getInput()
49 {
50 /* FUNCTION getInput */
51 int dataReadFlag;
52
53 dataReadFlag = (1 == scanf(" %u ", &b));
54 if (dataReadFlag)
55 {
56 /* more to read ? */
57 scanf(" %u %u ", &p, &m);
58 } /* more to read ? */
59 return (dataReadFlag);
60 } /* FUNCTION getInput */
61
62 /* r := b^p % m */
63
64 void process()
65 {
66 /* FUNCTION process */
67 long long i;
68 long long square;
69 long long goal;
70
71 if (1 == m)
72 {
73 /* if mod is 1 */
74 goal = 0;
75 } /* if mod is 1 */
76 else if ((0 == b) && (0 == p))
77 {
78 /* 0^0 is 1 */
79 goal = 1;
80 } /* 0^0 is 1 */
81 else if (0 == b)
82 {
83 /* 0^n == 0 */
84 goal = 0;
85 } /* 0^n == 0 */
86 else if (0 == p)
87 {
88 /* x^0 == 1 */
89 goal = 1;
90 } /* x^0 == 1 */
91 else
92 {
93 /* compute it */
94 b = b % m;
95 square = b;
96 goal = 1;
97 i = p;
98 while (0 < i)
99 {
100 /* while */
101 if (1 == (i & 1))
102 {
103 /* odd power */
104 goal = (goal * square) % m;
105 } /* odd power */
106 square = (square * square) % m;
107 i = i / 2;
108 } /* while */
109 } /* compute it */
110 printf("%u\n", goal);
111 } /* FUNCTION process */
112
113 int main()
114 {
115 /* main */
116 int moreToDo;
117
118 init();
119 moreToDo = getInput();
120 while (moreToDo)
121 {
122 /* while */
123 process();
124 moreToDo = getInput();
125 } /* while */
126
127 return EXIT_SUCCESS;
128 } /* main */
129