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;
}
}
Nie wiemy co to ma robić (Jakaś treść zadania?), ale po co Ci to cout<<d<<endl; w pętli?
poczatkowo mialem by sprawdzic, zapomnialem pozniej zmienic. juz poprawione. To jest https://pl.spoj.com/problems/PA05_POT/
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.
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;
}
}
Przecież Masz overflow tutaj: d=d*b;. Trzeba jednocześnie potęgować i brać resztę. Zrób research o modular exponentiation.
Wypisz sobie powiedzmy 10 kolejnych potęg danej liczby, i przyjrzyj się ostatnim cyfrom. Coś pewnie zauważysz.
policz klika kolejnych potęg (do 10) dla liczb od 0 do 9 i dojdź do ciekawych wniosków
Dzięki temu możesz dojść do rozwiązania działającego w O(1).
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:).
Nie czytałem odpowiedzi przed zrobieniem, jakoś zapomniałem o pytaniu na forum. W końcu zrobiłem to po swojemu, dziękuję wszystkim za odpowiedzi
#include<iostream>
using namespace std;
int main()
{
int a,b,c;
cin>>b;
for(int i=0;i<b;i++)
{
cin>>a>>c;
if(a%10==0)cout<<0<<endl;
if(a%10==1)cout<<1<<endl;
if(a%10==2)
{
if(c%4==0)cout<<6<<endl;
if(c%4==1)cout<<2<<endl;
if(c%4==2)cout<<4<<endl;
if(c%4==3)cout<<8<<endl;
}
if(a%10==3)
{
if(c%4==0)cout<<1<<endl;
if(c%4==1)cout<<3<<endl;
if(c%4==2)cout<<9<<endl;
if(c%4==3)cout<<7<<endl;
}
if(a%10==4)
{
if(c%2==0)cout<<6<<endl;
if(c%2==1)cout<<4<<endl;
}
if(a%10==5)cout<<5<<endl;
if(a%10==6)cout<<6<<endl;
if(a%10==7)
{
if(c%4==0)cout<<1<<endl;
if(c%4==1)cout<<7<<endl;
if(c%4==2)cout<<9<<endl;
if(c%4==3)cout<<3<<endl;
}
if(a%10==8)
{
if(c%4==0)cout<<6<<endl;
if(c%4==1)cout<<8<<endl;
if(c%4==2)cout<<4<<endl;
if(c%4==3)cout<<2<<endl;
}
if(a%10==9)
{
if(c%2==0)cout<<1<<endl;
if(c%2==1)cout<<9<<endl;
}
}
}