Advertisement
Guest User

Untitled

a guest
Mar 28th, 2020
135
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.56 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define ll unsigned long long
  3. #define s(n) scanf("%llu", &n);
  4. #define mod 1000007
  5. using namespace std;
  6.  
  7.  
  8. ll f(ll x, ll y)
  9. {
  10.     ll ans = 1, mul = x;
  11.     ll n = 1000;
  12.     while(y){  
  13.         if(y%2){
  14.             ans = (ans * mul) % n;
  15.         }
  16.         mul = (mul * mul) % n;
  17.         y/=2;
  18.     }
  19.     return ans;
  20. }
  21.  
  22. vector<short> multiply(std::vector<short> actual, vector<short> mul){
  23.     printf("in multiply\n");
  24.     vector<short> temp;
  25.     int asize = actual.size();
  26.     int mulsize = mul.size();
  27.  
  28.     int a, m, c, carry, st, in, i;
  29.     for(m = 0; m < mulsize; m++)
  30.     {
  31.         st = m; carry = 0;
  32.         if(m) c = temp.size();
  33.         else c = -1;
  34.         for(a = 0; a <asize; a++)
  35.         {
  36.             if(m == 0){
  37.                 in = (actual[a] * mul[m]) + carry;
  38.                 temp.push_back(in%10);
  39.                 carry = in / 10;
  40.             } else if(st < c) {
  41.                 in = (actual[a] * mul[m]) + carry + temp[st];
  42.                 temp[st++] = in % 10;
  43.                 carry = in / 10;
  44.             } else if(c>0 && st >=c){
  45.                 in = (actual[a] * mul[m]) + carry;
  46.                 temp.push_back(in % 10);
  47.                 carry = in / 10;
  48.             }
  49.         }
  50.         while(carry){
  51.             temp.push_back(carry % 10);
  52.             carry /= 10;
  53.         }
  54.     }
  55.    
  56.     return temp;
  57. }
  58.  
  59. std::vector<short> multiplier(std::vector<short> actual){
  60.     int mulsize = actual.size();
  61.     int asize = mulsize;
  62.     vector<short> mul;
  63.     for(int i=0; i<mulsize; i++) mul.push_back(actual[i]);
  64.  
  65.     std::vector<short> temp;
  66.    
  67.     int a, m, c, carry, st, in, i;
  68.     for(m = 0; m < mulsize; m++)
  69.     {
  70.         st = m; carry = 0;
  71.         if(m) c = temp.size();
  72.         else c = -1;
  73.         for(a = 0; a <asize; a++)
  74.         {
  75.             if(m == 0){
  76.                 in = (actual[a] * mul[m]) + carry;
  77.                 temp.push_back(in%10);
  78.                 carry = in / 10;
  79.             } else if(st < c) {
  80.                 in = (actual[a] * mul[m]) + carry + temp[st];
  81.                 temp[st++] = in % 10;
  82.                 carry = in / 10;
  83.             } else if(c>0 && st >=c){
  84.                 in = (actual[a] * mul[m]) + carry;
  85.                 temp.push_back(in % 10);
  86.                 carry = in / 10;
  87.             }
  88.         }
  89.         while(carry){
  90.             temp.push_back(carry % 10);
  91.             carry /= 10;
  92.         }
  93.     }
  94. }
  95.  
  96. ll sf(ll x, ll y)
  97. {
  98.     ll q=0;
  99.  
  100.     vector<short> actual, mul, ans;
  101.  
  102.     ll ac = x;
  103.     while(ac){
  104.  
  105.         mul.push_back(ac%10);
  106.         ac /= 10;
  107.     }
  108.         actual.push_back(1);
  109.     while(y){
  110.         if(y%2){
  111.             actual = multiply(actual, mul);
  112.            
  113.             // for(int i=actual.size()-1; i>=0; i--){
  114.             //  printf("%d", actual[i]);
  115.             // } printf("\n");
  116.         }
  117.         mul = multiply(mul, mul);
  118.         y/=2;
  119.     }
  120.  
  121.     long v = actual.size();
  122.  
  123.     for(long i = v-1, k=1; k<=3; i--, k++)
  124.     {
  125.         q += actual[i];
  126.         if(k<3) q*=10;
  127.     }
  128.     return q;
  129. }
  130.  
  131. int main()
  132. {
  133.     ll x, y, n;
  134.     ll test;
  135.  
  136.     s(test);
  137.     while(test--)
  138.     {
  139.         s(x); s(y);
  140.             printf("%llu...%.3llu\n", sf(x, y), f(x, y));
  141.  
  142.     }
  143.  
  144.  
  145.     return 0;
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement