Przekroczenie limitu czasu w potęgowaniu

0

Zrobiłem zadanie na potęgi : http://pl.spoj.pl/problems/PA05_POT/

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	double a, b;
	long long int pomoc;
	short testy;
	cin >> testy;
	while(testy)
	{
		cin >> a >> b;
		pomoc = pow(a,b);
		while(pomoc >= 10)
			pomoc = pomoc % 10;
		cout << pomoc << "\n";
	}
} 

NIBY wszystko dobrze, zgadza mi się wynik ale wywaliło mi że przekroczyłem limit czasu (1s). wtf ?
Jakieś propozycje ?

0
  • nie klep bruteforce'a na pałę
  • pomyśl zamiast klepać, weź pod uwagę właściwości operacji, które wykonujesz i tych, których są złożeniem
  • przeczytaj komentarze (przede wszystkim najnowszy) pod zadaniem
0

Możesz też spróbować zastosować szybkie potęgowanie modularne - http://www.algorytm.org/algorytmy-arytmetyczne/szybkie-potegowanie-modularne.html
Twój program nie jest dla tak wielkich liczb.

0

Podpowiem:

[email protected] ~ $ irb
>> (1..100).each {|i| puts i**2%10}
1
4
9
6
5
6
9
4
1
0
1
4
9
6
5
6
9
4
1
0
1
4
9
6
5
6
9
4
1
0
1
4
9
6
5
6
9
4
1
0
1
4
9
6
5
6
9
4
1
0
1
4
9
6
5
6
9
4
1
0
1
4
9
6
5
6
9
4
1
0
1
4
9
6
5
6
9
4
1
0
1
4
9
6
5
6
9
4
1
0
1
4
9
6
5
6
9
4
1
0
=> 1..100
0
allocer napisał(a)

Możesz też spróbować zastosować szybkie potęgowanie modularne - http://www.algorytm.org/algorytmy-arytmetyczne/szybkie-potegowanie-modularne.html
Twój program nie jest dla tak wielkich liczb.

Nie ma takiej potrzeby ;)
To ja też podpowiem: największe potęgowanie jakie może być potrzebne to 9^4

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