fork(5) download
copy 
  1. #include <iostream>
  2. #define SumOfDigits(x, y, z) x + y + z - 3 * '0'
  3. #define ProductOfDigits(x, y) (x[0] - '0') * (y[0] - '0')
  4. using namespace std;
  5.  
  6. void addFrontZeros(string &x, int numberOfZeros){
  7.     for(int i = 0; i < numberOfZeros; i++){
  8.         x = '0' + x;
  9.     }
  10. }
  11.  
  12. void addBackSideZeros(string &x, int numberOfZeros){
  13.     for(int i = 0; i < numberOfZeros; i++){
  14.         x = x + '0';
  15.     }
  16. }
  17.  
  18. void deleteFrontZeros(string &x){
  19.     while(x[0] == '0'){
  20.         x.erase(0, 1);
  21.     }
  22. }
  23.  
  24. int equalizeLength(string &x, string &y){
  25.     int difference = x.size() - y.size();
  26.  
  27.     if(difference > 0){
  28.         addFrontZeros(y, difference);
  29.     }
  30.     else{
  31.         addFrontZeros(x, -difference);
  32.     }
  33.  
  34.     return x.size();
  35. }
  36.  
  37. string add2Numbers(string x, string y){
  38.     string result = "0";
  39.     int length = equalizeLength(x, y);
  40.     int sum;
  41.  
  42.     addFrontZeros(result, length);
  43.  
  44.     for(int i = length - 1; i >= 0; i--){
  45.         sum = SumOfDigits(x[i], y[i], result[i + 1]);
  46.         result[i + 1] = '0' + sum % 10;
  47.         result[i] = '0' + sum / 10;
  48.     }
  49.  
  50.     deleteFrontZeros(result);
  51.  
  52.     return result;
  53. }
  54.  
  55. string add3Numbers(string x, string y, string z){
  56.     return add2Numbers(add2Numbers(x, y), z);
  57. }
  58.  
  59. // we know that x is bigger than y
  60. string subtract2Numbers(string x, string y){
  61.     string result = "0";
  62.     int length = equalizeLength(x, y);
  63.     int sum;
  64.  
  65.     addFrontZeros(result, length);
  66.  
  67.     for(int i = length - 1; i >= 0; i--){
  68.         sum = x[i] - y[i];
  69.  
  70.         if(sum < 0){
  71.             x[i - 1] -= 1;
  72.             sum += 10;
  73.         }
  74.  
  75.         result[i + 1] += sum;
  76.     }
  77.  
  78.     deleteFrontZeros(result);
  79.  
  80.     return result;
  81. }
  82.  
  83. string product2Numbers(string x, string y){
  84.     int length, sum, fh, sh;
  85.     string result , x1, x2, y1, y2, a, d, e;
  86.  
  87.     if(x == "0" || y == "0") return "0";
  88.  
  89.     length = equalizeLength(x, y);
  90.  
  91.     if(length == 0) return "0";
  92.     if(length == 1){
  93.         sum = ProductOfDigits(x, y);
  94.         if(sum >= 10){
  95.             result += ('0' + sum / 10);
  96.         }
  97.         result += ('0' + sum % 10);
  98.  
  99.         return result;
  100.     }
  101.  
  102.  
  103.     sh = length / 2;
  104.     fh = length - sh;
  105.  
  106.     x1 = x.substr(0, fh);
  107.     x2 = x.substr(fh, sh);
  108.  
  109.     y1 = y.substr(0, fh);
  110.     y2 = y.substr(fh, sh);
  111.  
  112.     a = product2Numbers(x1, y1);
  113.     d = product2Numbers(x2, y2);
  114.     e = product2Numbers(add2Numbers(x1, x2), add2Numbers(y1, y2));
  115.  
  116.     e = subtract2Numbers(e, add2Numbers(a, d));
  117.     addBackSideZeros(a, length - length % 2);
  118.     addBackSideZeros(e, length / 2);
  119.  
  120.     return add3Numbers(d, a, e);
  121. }
  122.  
  123. string decToBin(int n){
  124.     string x = "";
  125.  
  126.     while(n > 0){
  127.         if(n % 2 == 1){
  128.             x = '1' + x;
  129.         }
  130.         else{
  131.             x = '0' + x;
  132.         }
  133.         n /= 2;
  134.     }
  135.  
  136.     return x;
  137. }
  138.  
  139.  
  140. string exponentiation(string number, int exponent){
  141.     string exponentBINARY, solution="1";
  142.  
  143.     exponentBINARY = decToBin(exponent);
  144.  
  145.     if(number == "0"){
  146.         return "0";
  147.     }
  148.  
  149.     for(int i = exponentBINARY.size() - 1; i >= 0; i--){
  150.         if(exponentBINARY[i] == '1'){
  151.             solution = product2Numbers(solution, number);
  152.         }
  153.         if(i != 0){
  154.             number = product2Numbers(number, number);
  155.         }
  156.  
  157.  
  158.     }
  159.     deleteFrontZeros(solution);
  160.  
  161.     return solution;
  162. }
  163.  
  164. int main(){
  165.     string x;
  166.     int y;
  167.  
  168.     cin >> x >> y;
  169.     cout << exponentiation(x, y) << endl;
  170.  
  171. }
  172.  
Success #stdin #stdout 0s 4372KB
comments (?)
stdin
copy 
2 13
stdout
copy 
8192
https://ideone.com/iwqRnw
language:
C++ (gcc 8.3)
created:
6 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!