TC SRM 487 D1-250 CarrotJumping

Category: Brute Force, Mathematics
URL: http://www.topcoder.com/stat?c=problem_statement&pm=11022

class CarrotJumping {
public:
   int theJump(int);
};

long long MOD = 1000000007;

// compute 2^n (mod MOD)
long long pow(int v) {
   if (v == 0) return 1;
   if (v == 1) return 2;
   long long x = pow(v/2);
   if (v % 2 != 0) return (x * x * 2) % MOD;
   return (x * x) % MOD;
}

int CarrotJumping::theJump(int init) {
   int res = 100001;
   for (int a = 0; a <= 100000; a++) {
      for (int b = 0; b < 3; b++) {
         long long v = pow(a*3 + b*2);
         long long c = (v * init + (v - 1 + MOD) % MOD) % MOD;
         if (c == 0) {
            res <?= (a + b);
         }
      }
   }
   return res >= 100001 ? -1 : res;
}