Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define ll unsigned long long
- #define s(n) scanf("%llu", &n);
- #define mod 1000007
- using namespace std;
- ll f(ll x, ll y)
- {
- ll ans = 1, mul = x;
- ll n = 1000;
- while(y){
- if(y%2){
- ans = (ans * mul) % n;
- }
- mul = (mul * mul) % n;
- y/=2;
- }
- return ans;
- }
- vector<short> multiply(std::vector<short> actual, vector<short> mul){
- printf("in multiply\n");
- vector<short> temp;
- int asize = actual.size();
- int mulsize = mul.size();
- int a, m, c, carry, st, in, i;
- for(m = 0; m < mulsize; m++)
- {
- st = m; carry = 0;
- if(m) c = temp.size();
- else c = -1;
- for(a = 0; a <asize; a++)
- {
- if(m == 0){
- in = (actual[a] * mul[m]) + carry;
- temp.push_back(in%10);
- carry = in / 10;
- } else if(st < c) {
- in = (actual[a] * mul[m]) + carry + temp[st];
- temp[st++] = in % 10;
- carry = in / 10;
- } else if(c>0 && st >=c){
- in = (actual[a] * mul[m]) + carry;
- temp.push_back(in % 10);
- carry = in / 10;
- }
- }
- while(carry){
- temp.push_back(carry % 10);
- carry /= 10;
- }
- }
- return temp;
- }
- std::vector<short> multiplier(std::vector<short> actual){
- int mulsize = actual.size();
- int asize = mulsize;
- vector<short> mul;
- for(int i=0; i<mulsize; i++) mul.push_back(actual[i]);
- std::vector<short> temp;
- int a, m, c, carry, st, in, i;
- for(m = 0; m < mulsize; m++)
- {
- st = m; carry = 0;
- if(m) c = temp.size();
- else c = -1;
- for(a = 0; a <asize; a++)
- {
- if(m == 0){
- in = (actual[a] * mul[m]) + carry;
- temp.push_back(in%10);
- carry = in / 10;
- } else if(st < c) {
- in = (actual[a] * mul[m]) + carry + temp[st];
- temp[st++] = in % 10;
- carry = in / 10;
- } else if(c>0 && st >=c){
- in = (actual[a] * mul[m]) + carry;
- temp.push_back(in % 10);
- carry = in / 10;
- }
- }
- while(carry){
- temp.push_back(carry % 10);
- carry /= 10;
- }
- }
- }
- ll sf(ll x, ll y)
- {
- ll q=0;
- vector<short> actual, mul, ans;
- ll ac = x;
- while(ac){
- mul.push_back(ac%10);
- ac /= 10;
- }
- actual.push_back(1);
- while(y){
- if(y%2){
- actual = multiply(actual, mul);
- // for(int i=actual.size()-1; i>=0; i--){
- // printf("%d", actual[i]);
- // } printf("\n");
- }
- mul = multiply(mul, mul);
- y/=2;
- }
- long v = actual.size();
- for(long i = v-1, k=1; k<=3; i--, k++)
- {
- q += actual[i];
- if(k<3) q*=10;
- }
- return q;
- }
- int main()
- {
- ll x, y, n;
- ll test;
- s(test);
- while(test--)
- {
- s(x); s(y);
- printf("%llu...%.3llu\n", sf(x, y), f(x, y));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement