Задача "Тестирование"

Question

На первой строке вводят количество попыток тестирований N, следующие N линий вводятся числа K и M.

Вывод: на каждой строчке через пробел первые три и последние три цифры результата K^M. Ввод:

2

2 3

3 37

Вывод:

004 004

450 363

Ограничения: 1<= N <= 100000, 1 <= K, M <= 1000000

Мой вариант, проходит тесты но не все, проблема, мне кажется с размером вмещаемым в тип данных, как можно исправить?

#include <iostream> 
using namespace std;

int k, firstThree;
long long a;

unsigned long long dpow(unsigned long long N, unsigned long long M) {
    if (M == 0) {
        return 1;
    }   
    else if (M % 2 == 1) {
        return dpow(N, M - 1) * N;
    }
    else {
        unsigned long long temp = dpow(N, M / 2); 
        return temp * temp;
    }
}


void findResult(int store[], unsigned long long result) {
    if (result / 10 == 0) {
        cout << "00" << result << " " << "00" << result << endl;
    }
    else if (result / 100 == 0 && result / 10 != 0) {
        cout << "0" << result << " " << "0" << result << endl;
    }
    else if (result / 1000 == 0 && result / 10 != 0 && result / 100 == 0) {
        cout << result << " " << result << endl;
    }
    else {
        while (result != 0) {
            a = result % 10;
            if (k >= 0) {
                store[k--] = a;     
            }
            result /= 10;
            if (result > 99 && result < 1000) {
                firstThree = result;
            }
        
            if (k < 0 && firstThree != 0) {
                cout << firstThree << " " << flush;
                for (int i = 0; i < 3; i++) {
                    cout << store[i] << flush;
                }
                cout << endl;
                break;
            }
        } 
    }   
}



int main () {
    
    int T;
    unsigned long long N, M;
    int* store;
    unsigned long long result;
    cin >> T;
    
    for (int i = 0; i < T; i++) {
        cin >> N >> M;
        
        result = dpow(N, M);
        store = new int[3];
        firstThree = 0;
        k = 2;
        
        findResult(store, result);
        delete []store;
    }
    
    return 0;
}

Answer 1

Ну, примерно так (только оттестироваться мне было не на чем, да и спешу, мне бежать надо...)

#include <iostream>
#include <cmath>
#include <string>

using namespace std;

//// Быстрое возведение в степень по модулю p
unsigned int iqpow(unsigned int x, unsigned int e, unsigned int p)
{
    unsigned int res = 1;
    x %= p;
    for(;e;e>>=1)
    {
        if (e&1) res = (res*x)%p;
        x = (x*x)%p;
    }
    return res;
}


void solve(unsigned int K, unsigned int M)
{
    string f, l;
    double x = M*log10(K);
    if (x < 7)  // В лоб
    {
        string s = to_string(iqpow(K,M,1000000000));
        f = s.substr(0,3);
        l = (s.size() < 3) ? s.substr(0,3) : s.substr(s.size()-3,3);
    }
    else
    {
        l = to_string(iqpow(K,M,1000));
        x -= floor(x);
        f = to_string(pow(10,x)*100).substr(0,3);
    }
    while(f.size() < 3) f = "0" + f;
    while(l.size() < 3) l = "0" + l;
    cout << f << " " << l << "\n";
}


int main()
{
    int N; cin >> N;
    for(int i = 0; i < N; ++i)
    {
        unsigned int K, M;
        cin >> K >> M;

        solve(K,M);
    }
}

БЛОГ НА HUSL

Задача "Тестирование"

Ответы (1 шт):