Poprawienie programu.

Question

Jak mogę poprawić mój program, żeby zmusić go do szybszego działania. Głównie chodzi mi o to, żeby strona: https://pl.spoj.com/problems/PA05_POT/ i ich internetowy sędzia nie odrzucał mojego programu z względu na czas.

Mój program:

---

 

---

#include <iostream>
using namespace std;
int n;
long long a,b;
long long x(long long a,long long b)
{
    long long p=1;
    for (int i=0;i<b;i++)
        p*=a;

    return p;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
    cin>>a>>b;
    cout<<x(a,b)%10<<endl;
    }
    return 0;
}

---

 

---

 

Answer 1

Pomnożenie liczby przez siebie miliard razy z natury nie wykona się zbyt szybko.

W zadaniu chodzi o wyznaczenie tylko ostatniej cyfry. Rekomenduję zastanowić się przy tym z kartką i długopisem - to jest bardziej temat matematyczny niż kodowanie.

Comments

(pozwoliłem sobie schować ten komentarz - nie po to sugeruję spróbować rozwiązać to na kartce, żeby w komentarzu była odpowiedź na tacy jak do tego podejść. Patrz na odpowiedź Sebastiana w Twoim linku.)

---

Dziękuję, udało się!

 

Na pewno da się łatwiej to napisać, ale ważne, że sam to zrobiłem.

#include <iostream>
#include <string>
using namespace std;
string a;
int b,d,n;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
    cin>>a>>b;
    //jeżeli ostatnia cyfra liczby "a" jest jakaś to
    d=a.length();
    if(a[d-1]=='0')
        cout<<0<<endl;
    if(a[d-1]=='1')
        cout<<1<<endl;
    if(a[d-1]=='5')
        cout<<5<<endl;
    if(a[d-1]=='6')
        cout<<6<<endl;

        if(a[d-1]=='4')
        {
            if(b%2==0)
                cout<<6<<endl;
            else
                cout<<4<<endl;
        }
        if(a[d-1]=='9')
        {
            if(b%2==0)
                cout<<1<<endl;
            else
                cout<<9<<endl;
        }
        if(a[d-1]=='2')
        {

            if((b%2==0)&&(b%4!=0))
                cout<<4<<endl;
            else
           if(b%4==0)
                cout<<6<<endl;
            else
           if(b%4==1)
                cout<<2<<endl;
           else
           if(b%4==3)
                cout<<8<<endl;
        }
        if(a[d-1]=='3')
        {

            if((b%2==0)&&(b%4!=0))
                cout<<9<<endl;
            else
           if(b%4==1)
                cout<<3<<endl;
            else
           if(b%4==0)
                cout<<1<<endl;
           else
            if(b%4==3)
                cout<<7<<endl;
        }
            if(a[d-1]=='7')
        {

            if((b%2==0)&&(b%4!=0))
                cout<<9<<endl;
            else
           if(b%4==1)
                cout<<7<<endl;
            else
           if(b%4==0)
                cout<<1<<endl;
           else
            if(b%4==3)
                cout<<3<<endl;
        }
        if(a[d-1]=='8')
        {

            if((b%2==0)&&(b%4!=0))
                cout<<4<<endl;
            else
           if(b%4==1)
                cout<<8<<endl;
            else
           if(b%4==0)
                cout<<6<<endl;
           else
            if(b%4==3)
                cout<<2<<endl;
        }

    }
    return 0;
}

 

---

@RSG00 Kod możesz skrócić kilka razy używając tablicy ;)