-
Notifications
You must be signed in to change notification settings - Fork 0
/
SPOTWO.c
68 lines (59 loc) · 1.3 KB
/
SPOTWO.c
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
#include <stdio.h>
#define LIMIT 20
#define DIVISOR 1000000007
#define READ_INT(_x) \
{ \
int _tmp = 0; \
register int _ch = getchar_unlocked(); \
while (_ch < 48 || _ch > 57) \
_ch = getchar_unlocked(); \
while (48 <= _ch && _ch <= 57) \
{ \
_tmp = (_tmp << 3) + (_tmp << 1) + _ch - 48; \
_ch = getchar_unlocked(); \
} \
(_x) = _tmp; \
} \
char _str[10];
#define WRITE_INT(_x) \
{ \
register int _i = 0; \
int _tmp = (_x); \
do \
{ \
*(_str + _i++) = _tmp % 10 + 48; \
_tmp /= 10; \
} while (_tmp != 0); \
for (_i--; _i >= 0; _i--) \
putchar_unlocked(*(_str + _i)); \
} \
int main(void)
{
int a[LIMIT];
long long p, tmp;
int i, n, t;
for (*a = p = 4, i = 1; i < LIMIT; i++)
{
p = tmp = p * p % DIVISOR;
p = p * p % DIVISOR;
p = p * p % DIVISOR;
*(a + i) = p = p * tmp % DIVISOR;
}
#ifdef DEBUG
printf("a: ");
for (i = 0; i < LIMIT; i++)
printf("%d ", *(a + i));
printf("\n");
#endif
READ_INT(t);
while (t--)
{
READ_INT(n);
for (p = 1, i = 0; n > 0; n >>= 1, i++)
if ((n & 0x1) != 0)
p = *(a + i) * p % DIVISOR;
WRITE_INT(p);
putchar_unlocked('\n');
}
return 0;
}