Przekroczono limit czasu SPOJ – co zmienić, aby było dobrze?

0

Jestem poczatkujacym, na spoj przekroczylem limit czasu, wiecie co zmienic by bylo ok?

#include <iostream>
using namespace std;
int main()
{
 int a,b,c,d=1;
 cin>>a;
for(int i=0;i<a;i++)
{
    d=1;
    cin>>b;
    cin>>c;

    for(int j=1;j<=c;j++)
    {
        d=d*b;
    }
cout<<d<<endl;
}
}
2

Nie wiemy co to ma robić (Jakaś treść zadania?), ale po co Ci to cout<<d<<endl; w pętli?

0

poczatkowo mialem by sprawdzic, zapomnialem pozniej zmienic. juz poprawione. To jest https://pl.spoj.com/problems/PA05_POT/

4

He, Chciałeś bilion do bilionowej podnieść w 31 bitach! To chyba by zaczęły gasnąć gwiazdy, jakby Ci się udało:) Ale na szczęście Masz znaleźć tylko ostatnią cyfrę. Zainteresuj się operatorem modulo i modular exponentiation.

0

Jakoś prościej by się dało może? Zapomniałem o tym że tylko ostatnia cyfra ma być pokazana. Na razie skleciłem taki program ale nadal jest za wolny.

#include <iostream>
using namespace std;
int main()
{
 int a,b,c,d=1;
 cin>>a;
for(int i=0;i<a;i++)
{
    d=1;
    cin>>b;
    cin>>c;

    for(int j=1;j<=c;j++)
    {
        d=d*b;

    }
cout<<d%10<<endl;
}
}
2

Przecież Masz overflow tutaj: d=d*b;. Trzeba jednocześnie potęgować i brać resztę. Zrób research o modular exponentiation.

2

Wypisz sobie powiedzmy 10 kolejnych potęg danej liczby, i przyjrzyj się ostatnim cyfrom. Coś pewnie zauważysz.

3

policz klika kolejnych potęg (do 10) dla liczb od 0 do 9 i dojdź do ciekawych wniosków

1

Dzięki temu możesz dojść do rozwiązania działającego w O(1).

0

Dobra, wytłumaczę Ci to, ale się Nauczysz i następne Robisz sam:). Zadania na SPOJu nie są takie, że wpisac byle co i wysłać, trzeba się trochę pomęczyć ze złożonością:). Jakbyś Czytał to co koledzy piszą, to na kartce powinieneś dojść, co najmniej, do naiwnego rozwiązania (które na 100% nie przejdzie):

int mod_power1(int a, int n, int mod){
    int p = 1;
    for (int i = 0; i < n; i++){
        p = (a * p) % mod;
    }
    return p;
}

Jak widać złożoność jest O(n), dalej za dużo przy liczbach do miliarda. Trzeba lepiej potęgować, chyba najłatwiejszy z algorytmów dziel i rządź i jednocześnie efektywny jako potęgowanie, to: squaring exponentiation. Łatwo go przepisać do wersji z modulo, trzeba sobie tylko dodać funkcję mnożenia mod:

int mod_mul(int n, int m, int mod){
    return ( (n % mod) * (m % mod)) % mod;
}

int mod_power2(int a, int n, int mod){
        if (n == 1)  {return a % mod;}
        else if (n % 2 != 0){
        return mod_mul(a, mod_power2(mod_mul(a, a, mod), (n - 1) / 2, mod), mod);}
        else{
        return mod_power2(mod_mul(a, a, mod), n / 2, mod);}
}

Kod nie jest optymalny, ale złożoność jest O(logn), na SPOJU na pewno przejdzie:).

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