cses

cses solutions in pure c
git clone git://git.superpozycja.net/cses
log | files | refs

s.c (799B)

      1 #include <stdio.h>
      2 #include <stdlib.h>
      3 #include <string.h>
      4 #include <stdint.h>
      5 
      6 #define MOD 1000000007
      7 
      8 int solve()
      9 {
     10 	uint32_t n;
     11 	uint64_t res = 1;
     12 	scanf("%u", &n);
     13 
     14 	n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1);
     15 	n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2);
     16 	n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4);
     17 	n = ((n >> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8);
     18 	n = ( n >> 16             ) | ( n               << 16);
     19 
     20 	int r;
     21 	float f = (float) ( n & -n );
     22 	r = (*(uint32_t *)&f >> 23) - 0x7f;
     23 	n >>= r;
     24 
     25 	for (int i = 0; i < 32 - r; i++) {
     26 		if (n & 1) {
     27 			res *= res;
     28 			res %= MOD;
     29 			res <<= 1;
     30 			res %= MOD;
     31 		}
     32 		else {
     33 			res *= res;
     34 			res %= MOD;
     35 		}
     36 		n >>= 1;
     37 	}
     38 	printf("%llu\n", res);
     39 
     40 	return 0;
     41 }
     42 
     43 int main()
     44 {
     45 	int t = 1;
     46 	while (t--)
     47 		solve();
     48 }