fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. //#include <string.h>
  4. #include <vector>
  5. //#include <ctime>
  6. #define SumOfDigits(x, y, z) x + y + z - 3 * '0'
  7. #define ProductOfDigits(x, y) (x[0] - '0') * (y[0] - '0')
  8. #define Product2Digits(x, y) (x - '0') * (y - '0')
  9. //#define ProductDigits(x, y) (x - '0') * (y - '0')
  10. using namespace std;
  11.  
  12. vector<int> deleteFrontZeros(vector<int> numberArray){
  13.     while(numberArray[0] == 0 && numberArray.size() > 1){
  14.         numberArray.erase(numberArray.begin());
  15.     }
  16.  
  17.     return numberArray;
  18. }
  19.  
  20. vector<int> addFrontZeros(vector<int> numberArray, int numberOfZeros){
  21.     for(int i = 0; i < numberOfZeros; i++){
  22.         numberArray.insert(numberArray.begin(), 0);
  23.     }
  24.  
  25.     return numberArray;
  26. }
  27.  
  28. string vector2string(vector<int> numberArray){
  29.     string number="";
  30.  
  31.     for(int i = 0; i < numberArray.size(); i++){
  32.         number += (numberArray[i] + '0');
  33.     }
  34.  
  35.     return number;
  36. }
  37.  
  38. vector<int> string2Vector(string number){
  39.     vector<int> numberArray={};
  40.  
  41.     for(int i = 0; i < number.size(); i++){
  42.         numberArray.push_back(number[i] - '0');
  43.     }
  44.  
  45.     return numberArray;
  46. }
  47.  
  48. vector<int> number2Array(int number){
  49.     vector<int> numberArray;
  50.     numberArray.clear();
  51.  
  52.     if(number == 0)
  53.         return {0};
  54.  
  55.     while(number > 0){
  56.         numberArray.insert(numberArray.begin(), number % 10);
  57.         number /= 10;
  58.     }
  59.  
  60.     return numberArray;
  61. }
  62.  
  63. int equalizeLength(vector<int> &x, vector<int> &y){
  64.     int difference = x.size() - y.size();
  65.  
  66.     if(difference > 0){
  67.         y = addFrontZeros(y, difference);
  68.     }
  69.     else{
  70.         x = addFrontZeros(x, -difference);
  71.     }
  72.  
  73.     return x.size();
  74. }
  75.  
  76. vector<int> add2Numbers(vector<int> result, int number, int displacement){
  77.     int sum;
  78.  
  79.     for(int i = result.size() - 1 - displacement; i >= 0; ){
  80.         sum = result[i] + number % 10;
  81.         result[i] = sum % 10;
  82.         result[i - 1] += (sum / 10);
  83.         number /= 10;
  84.         if(number == 0){
  85.             i = -1;
  86.         }
  87.         else{
  88.             i--;
  89.         }
  90.     }
  91.  
  92.     return result;
  93. }
  94.  
  95. vector<int> addBackSideZeros(vector<int> numberArray, int numberOfZeros){
  96.     for(int i = 0; i < numberOfZeros; i++){
  97.         numberArray.push_back(0);
  98.     }
  99.  
  100.     return numberArray;
  101. }
  102.  
  103. void addFrontZeros(string &x, int numberOfZeros){
  104.     for(int i = 0; i < numberOfZeros; i++){
  105.         x = '0' + x;
  106.     }
  107. }
  108.  
  109. void addBackSideZeros(string &x, int numberOfZeros){
  110.     for(int i = 0; i < numberOfZeros; i++){
  111.         x = x + '0';
  112.     }
  113. }
  114.  
  115. void deleteFrontZeros(string &x){
  116.     while(x[0] == '0'){
  117.         x.erase(0, 1);
  118.     }
  119. }
  120.  
  121. int equalizeLength(string &x, string &y){
  122.     int difference = x.size() - y.size();
  123.  
  124.     if(difference > 0){
  125.         addFrontZeros(y, difference);
  126.     }
  127.     else{
  128.         addFrontZeros(x, -difference);
  129.     }
  130.  
  131.     return x.size();
  132. }
  133.  
  134. string add2Numbers(string x, string y){
  135.     string result = "0";
  136.     int length = equalizeLength(x, y);
  137.     int sum;
  138.  
  139.     addFrontZeros(result, length);
  140.  
  141.     for(int i = length - 1; i >= 0; i--){
  142.         sum = SumOfDigits(x[i], y[i], result[i + 1]);
  143.         result[i + 1] = '0' + sum % 10;
  144.         result[i] = '0' + sum / 10;
  145.     }
  146.  
  147.     deleteFrontZeros(result);
  148.  
  149.     return result;
  150. }
  151.  
  152. string add3Numbers(string x, string y, string z){
  153.     return add2Numbers(add2Numbers(x, y), z);
  154. }
  155.  
  156. // we know that x is bigger than y
  157. string subtract2Numbers(string x, string y){
  158.     string result = "0";
  159.     int length = equalizeLength(x, y);
  160.     int sum;
  161.  
  162.     addFrontZeros(result, length);
  163.  
  164.     for(int i = length - 1; i >= 0; i--){
  165.         sum = x[i] - y[i];
  166.  
  167.         if(sum < 0){
  168.             x[i - 1] -= 1;
  169.             sum += 10;
  170.         }
  171.  
  172.         result[i + 1] += sum;
  173.     }
  174.  
  175.     deleteFrontZeros(result);
  176.  
  177.     return result;
  178. }
  179.  
  180. string product2Digits(string x, string y){
  181.     string result = "";
  182.     int sum;
  183.  
  184.     sum = ProductOfDigits(x, y);
  185.     if(sum >= 10){
  186.         result += ('0' + sum / 10);
  187.     }
  188.     result += ('0' + sum % 10);
  189.  
  190.     return result;
  191. }
  192.  
  193. string product2Numbers(string x, string y){
  194.     int length, fh, sh, sum, difference;
  195.     string result, x1, x2, y1, y2, a, d, e;
  196.  
  197.     if(x == "0" || y == "0") return "0";
  198.  
  199.     difference = x.size() - y.size();
  200.  
  201.     if(difference > 0){
  202.         for(int i = difference; i--;)
  203.             y = '0' + y;
  204.     }
  205.     else{
  206.         for(int i = -difference; i--;)
  207.             x = '0' + x;
  208.     }
  209.  
  210.     length = x.size();
  211.  
  212.     if(length == 0) return "0";
  213.     if(length == 1){
  214.         result="";
  215.         sum = (x[0] - '0') * (y[0] - '0');
  216.         if(sum >= 10){
  217.             result += ('0' + sum / 10);
  218.         }
  219.         result += ('0' + sum % 10);
  220.  
  221.         return result;
  222.     }
  223.  
  224.  
  225.     sh = length / 2;
  226.     fh = length - sh;
  227.  
  228.     x1 = x.substr(0, fh);
  229.     x2 = x.substr(fh, sh);
  230.  
  231.     y1 = y.substr(0, fh);
  232.     y2 = y.substr(fh, sh);
  233.  
  234.     a = product2Numbers(x1, y1);
  235.     d = product2Numbers(x2, y2);
  236.     e = product2Numbers(add2Numbers(x1, x2), add2Numbers(y1, y2));
  237.  
  238.     e = subtract2Numbers(e, add2Numbers(a, d));
  239.     addBackSideZeros(a, length - length % 2);
  240.     addBackSideZeros(e, length / 2);
  241.  
  242.     return add3Numbers(d, a, e);
  243. }
  244.  
  245. string product2NumbersGreedy(string x, string y){
  246.     vector<int> result = {0}, X, Y;
  247.     int displacement;
  248.  
  249.     X = string2Vector(x);
  250.     Y = string2Vector(y);
  251.     result = addFrontZeros(result, x.size() + y.size());
  252.  
  253.     for(int i = x.size() - 1; i >= 0; i--){
  254.         displacement = x.size() - i - 1;
  255.         for(int j = y.size() - 1; j >= 0; j--){
  256.             result = add2Numbers(result, X[i] * Y[j], displacement);
  257.             displacement++;
  258.         }
  259.     }
  260.  
  261.     result = deleteFrontZeros(result);
  262.  
  263.     return vector2string(result);
  264. }
  265.  
  266. string decToBin(int n){
  267.     string x = "";
  268.  
  269.     while(n > 0){
  270.         if(n % 2 == 1){
  271.             x = '1' + x;
  272.         }
  273.         else{
  274.             x = '0' + x;
  275.         }
  276.         n /= 2;
  277.     }
  278.  
  279.     return x;
  280. }
  281.  
  282. string exponentiation(string number, int exponent){
  283.     string exponentBINARY, solution="1";
  284.  
  285.     exponentBINARY = decToBin(exponent);
  286.  
  287.     if(number == "0"){
  288.         return "0";
  289.     }
  290.  
  291.     for(int i = exponentBINARY.size() - 1; i >= 0; i--){
  292.         if(exponentBINARY[i] == '1'){
  293.             solution = product2NumbersGreedy(solution, number);
  294.         }
  295.         if(i != 0){
  296.             number = product2NumbersGreedy(number, number);
  297.         }
  298.  
  299.  
  300.     }
  301.     deleteFrontZeros(solution);
  302.  
  303.     return solution;
  304. }
  305.  
  306. int main(){
  307.     ios::sync_with_stdio(false);
  308.     string x, z;
  309.     int y;
  310.  
  311.     cin >> x >> y;
  312.     //clock_t beginning = clock();
  313.  
  314.     z = exponentiation(x, y);
  315.  
  316.     //clock_t ending = clock();
  317.  
  318.     cout << z << endl;
  319.     //cout << (ending - beginning);
  320.  
  321.  
  322. }
  323.  
Success #stdin #stdout 0s 4560KB
comments (?)
stdin
copy 
2 6
stdout
copy 
64
https://ideone.com/n8WGYv
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!