fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string.h>
  4. #include <vector>
  5. #define SumOfDigits(x, y, z) x + y + z - 3 * '0'
  6. using namespace std;
  7.  
  8. vector<int> number2Array(int number){
  9.     vector<int> numberArray;
  10.     numberArray.clear();
  11.  
  12.     if(number == 0)
  13.         return {0};
  14.  
  15.     while(number > 0){
  16.         numberArray.insert(numberArray.begin(), number % 10);
  17.         number /= 10;
  18.     }
  19.  
  20.     return numberArray;
  21. }
  22.  
  23. vector<bool> decToBin(int n){
  24.     vector<bool> binNumber;
  25.     binNumber.clear();
  26.  
  27.     while(n > 0){
  28.         if(n % 2 == 1){
  29.             binNumber.insert(binNumber.begin(), true);
  30.         }
  31.         else{
  32.              binNumber.insert(binNumber.begin(), false);
  33.         }
  34.         n /= 2;
  35.     }
  36.  
  37.     return binNumber;
  38. }
  39.  
  40. vector<int> addFrontZeros(vector<int> numberArray, int numberOfZeros){
  41.     for(int i = 0; i < numberOfZeros; i++){
  42.         numberArray.insert(numberArray.begin(), 0);
  43.     }
  44.  
  45.     return numberArray;
  46. }
  47.  
  48. vector<int> addBackSideZeros(vector<int> numberArray, int numberOfZeros){
  49.     for(int i = 0; i < numberOfZeros; i++){
  50.         numberArray.push_back(0);
  51.     }
  52.  
  53.     return numberArray;
  54. }
  55.  
  56. vector<int> deleteFrontZeros(vector<int> numberArray){
  57.     while(numberArray[0] == 0 && numberArray.size() > 1){
  58.         numberArray.erase(numberArray.begin());
  59.     }
  60.  
  61.     return numberArray;
  62. }
  63.  
  64. int equalizeLength(vector<int> &x, vector<int> &y){
  65.     int difference = x.size() - y.size();
  66.  
  67.     if(difference > 0){
  68.         y = addFrontZeros(y, difference);
  69.     }
  70.     else{
  71.         x = addFrontZeros(x, -difference);
  72.     }
  73.  
  74.     return x.size();
  75. }
  76.  
  77. vector<int> add2Numbers(vector<int> x, vector<int> y){
  78.     vector<int> result;
  79.     int length = equalizeLength(x, y);
  80.     int sum;
  81.  
  82.     result.clear();
  83.     result = addFrontZeros(result, length + 1);
  84.  
  85.     for(int i = length - 1; i >= 0; i--){
  86.         sum = x[i] + y[i] + result[i + 1];
  87.         result[i + 1] = sum % 10;
  88.         result[i] = sum / 10;
  89.     }
  90.  
  91.     result = deleteFrontZeros(result);
  92.  
  93.     return result;
  94. }
  95.  
  96. vector<int> add3Numbers(vector<int> x, vector<int> y, vector<int> z){
  97.     return add2Numbers(add2Numbers(x, y), z);
  98. }
  99.  
  100. // we know that x is bigger than y
  101. vector <int> subtract2Numbers(vector <int> x, vector<int> y){
  102.     vector<int> result;
  103.     int length = equalizeLength(x, y), sum;
  104.  
  105.     result.clear();
  106.     result = addFrontZeros(result, length);
  107.  
  108.  
  109.     for(int i = length - 1; i >= 0; i--){
  110.         sum = x[i] - y[i];
  111.  
  112.         if(sum < 0){
  113.             x[i - 1] -= 1;
  114.             sum += 10;
  115.         }
  116.  
  117.         result[i] = sum;
  118.     }
  119.  
  120.     result = deleteFrontZeros(result);
  121.  
  122.     return result;
  123. }
  124.  
  125. vector<int> product2Numbers(vector<int> x, vector<int> y){
  126.     int length, fh, sh;
  127.     vector<int> a, d, e;
  128.     vector<int>::iterator firstX1, firstX2, lastX1, lastX2, firstY1, firstY2, lastY1, lastY2;
  129.  
  130.     if((x[0] == 0  && x.size() == 1)|| (y[0] == 0 && y.size() == 1)) return {0};
  131.  
  132.     length = equalizeLength(x, y);
  133.  
  134.     if(length == 0) return {0};
  135.     if(length == 1){
  136.         return number2Array(x[0] * y[0]);
  137.     }
  138.  
  139.     sh = length / 2;
  140.     fh = length - sh;
  141.  
  142.     firstX1 = x.begin();
  143.     lastX1 = x.begin() + fh;
  144.  
  145.     firstX2 = x.begin() + fh;
  146.     lastX2 = x.begin() + fh + sh;
  147.  
  148.     firstY1 = y.begin();
  149.     lastY1 = y.begin() + fh;
  150.  
  151.     firstY2 = y.begin() + fh;
  152.     lastY2 = y.begin() + fh + sh;
  153.  
  154.     vector<int> x1(firstX1, lastX1), x2(firstX2, lastX2), y1(firstY1, lastY1), y2(firstY2, lastY2);
  155.  
  156.     /*for(int i = 0;i < x1.size(); i++)
  157.         cout << x1[i];
  158.     cout << ' ';
  159.     for(int i = 0;i < x2.size(); i++)
  160.         cout << x2[i];
  161.     cout << ' ';
  162.     for(int i = 0;i < y1.size(); i++)
  163.         cout << y1[i];
  164.     cout << ' ';
  165.     for(int i = 0;i < y2.size(); i++)
  166.         cout << y2[i];
  167.     cout << endl;
  168.  
  169.     cout << x1.size() << ' ' << x2.size() << ' ' << y1.size() << ' ' << y2.size() << endl;
  170.     */
  171.     a = product2Numbers(x1, y1);
  172.     d = product2Numbers(x2, y2);
  173.     e = product2Numbers(add2Numbers(x1, x2), add2Numbers(y1, y2));
  174.  
  175.     e = subtract2Numbers(e, add2Numbers(a, d));
  176.     a = addBackSideZeros(a, length - length % 2);
  177.     /*for(int i = 0;i < a.size(); i++)
  178.         cout << a[i];
  179.     cout << endl;*/
  180.     e = addBackSideZeros(e, length / 2);
  181.     /*for(int i = 0;i < e.size(); i++)
  182.         cout << e[i];
  183.     cout << endl;*/
  184.  
  185.     return add3Numbers(d, a, e);
  186. }
  187.  
  188. vector<int> product2NumbersGreedy(vector<int> x, vector<int> y){
  189.     vector<int> result, help;
  190.     int zerosToAppend, sum;
  191.  
  192.     for(int i = x.size() - 1; i >= 0; i--){
  193.         zerosToAppend = x.size() - i - 1;
  194.         for(int j = y.size() - 1; j >= 0; j--){
  195.             help = number2Array(x[i] * y[j]);
  196.             help = addBackSideZeros(help, zerosToAppend);
  197.             result = add2Numbers(result, help);
  198.             zerosToAppend++;
  199.         }
  200.     }
  201.     return result;
  202. }
  203.  
  204. string exponentiation(int number, int exponent){
  205.     vector<bool> exponentBinary;
  206.     vector<int> solution = {1}, numberArray;
  207.     string finish="";
  208.  
  209.     exponentBinary.clear();
  210.     exponentBinary = decToBin(exponent);
  211.     numberArray = number2Array(number);
  212.  
  213.     if(number == 0){
  214.         return "0";
  215.     }
  216.  
  217.     for(int i = exponentBinary.size() - 1; i >= 0; i--){
  218.         if(exponentBinary[i] == true){
  219.             solution = product2NumbersGreedy(solution, numberArray);
  220.         }
  221.         if(i != 0){
  222.             numberArray = product2NumbersGreedy(numberArray, numberArray);
  223.         }
  224.     }
  225.     solution = deleteFrontZeros(solution);
  226.  
  227.     for(int i = 0; i < solution.size(); i++)
  228.         finish += (solution[i] + '0');
  229.  
  230.     return finish;
  231.  
  232. }
  233. int main(){
  234.     ios::sync_with_stdio(false);
  235.     int x, y;
  236.  
  237.     cin >> x >> y;
  238.     cout << exponentiation(x, y);
  239.     vector<int> z;
  240.  
  241.     /*z = product2Numbers({1, 4, 4}, {1, 2});
  242.     for(int i = 0; i < z.size(); i++){
  243.         cout << z[i];
  244.     }*/
  245.  
  246. }
  247.  
Time limit exceeded #stdin #stdout 5s 4508KB
comments (?)
stdin
copy 
999 998
stdout
copy 
Standard output is empty
https://ideone.com/zwRstK
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!