Dziwne potęgowanie

1

Treść zadania:
https://pl.spoj.com/problems/PA05_POT/

Algorytm:
https://en.wikipedia.org/wiki/Modular_exponentiation

Lista znalezionych w tym wątku błędów:

  • liczenie potęgi przy pomocy liczb zmienno-przecinkowych (szybko straci się dokładność)
  • liczenie w pętli (zarówno a jak i b mogą być 1E9)
  • brak modulo na początku
  • nie zastosowanie ww. podstaw matematycznych
1

Ech, wiecie, że potęgowanie w tym zadaniu powinno być wykonane w O(1)?

1

Z tego co pamietam, to z potęgowaniem modularnym rozwiązanie przechodziło, złożoność O(30); @enedil czemu O(10)? Potęgowanie modularne jest O(log(n)), (z miliarda 30). Ale można to zrobić lepiej:
https://duckduckgo.com/?t=can[...]ion&atb=v219-1&ia=web

0

Ja zrobiłem to tak:

#include <iostream>
#include <vector>
#include <utility>

int pow(int a, int b)
{
    int p = 1;

    for (int i = 0; i < b; i++)
        p *= a;

    return p;
}

int main()
{
    using namespace std;

    long long ile;
    cin >> ile;

    vector<pair<int, int> > ab;

    for (int i = 0; i < ile; i++)
    {
        int a, b;
        cin >> a >> b;
        ab.push_back(make_pair(a, b));
    }

    long long potegi[31] = {1}; // potegi[0] -> ^1

    for (int i = 1; i < 31; i++)
        potegi[i] = potegi[i - 1] * 2;

    for (int i = 0; i < ile; i++)
    {
        int reszty[31] = {0};

        reszty[0] = pow(ab[i].first, 1) % 10;

        for (int j = 1; j < 31; j++)
        {
            reszty[j] = pow(reszty[j - 1], 2) % 10; // reszty[0] -> a ^ 1
        }

        long long sumaPoteg = 0;
        long long reszta = 1;

        for (int k = 30; sumaPoteg < ab[i].second; k--)
        {
            if (sumaPoteg + potegi[k] > ab[i].second)
                continue;

            sumaPoteg += potegi[k];
            reszta = (reszta * reszty[k]) % 10;
        }

        cout << reszta << endl;
    }

    return 0;
}

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0