fork download
copy 
  1. #include<iostream>
  2. using namespace std;
  3.  
  4.     long long int fast_exp(int base, int exp)
  5.     {
  6.         if(exp==1)
  7.         return base;
  8.         else
  9.         {
  10.             if(exp%2 == 0)
  11.             {
  12.                 long long int ret = fast_exp(base, exp/2);
  13.                 long long int base1 = ret * ret;
  14.                 return base1 % 1000000007;
  15.             }
  16.             else
  17.             {
  18.                 long long int ret = fast_exp(base, (exp-1)/2);
  19.                 long long int ans = base * ret;
  20.                 ans %= 1000000007; 
  21.                 ans *= ret;
  22.                 return ans % 1000000007;
  23.             }
  24.         }
  25.     }
  26.  
  27. int main() {
  28. 	std::cout << fast_exp(2, 999999999) << std::endl;
  29. 	std::cout << fast_exp(2, 1000000000) << std::endl;
  30. 	return 0;
  31. }
Success #stdin #stdout 0s 3340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
570312504
140625001
https://ideone.com/aoHJd8
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!