Zadanie w SPOJu

Mam problem z pewnym zadaniem ze spoja.
Link: https://pl.spoj.pl/problems/PA05_POT/

Problem polega na tym, że wywala mi błąd: Błędna Odpowiedź.
Oto kod mojego programu:

// Kod na wxDev-C++
#include <iostream>
using namespace std;
int main()
{
	register unsigned long long zm1 = 0;
	register unsigned long long zm2 = 0;
	register unsigned short stopien = 0;
    register unsigned short t = 0;
	cin >> t;
	while(t--)
	{
		cin >> zm1 >> stopien;
		stopien--;
		zm1 %= 10;
		zm2 = zm1;
		while(stopien--)
		zm1*=zm2;
		cout << (zm1%10) << endl;
	}
}

Próbowałem już użyć pow'a z cmath'a...
Na nic.
A program przecież robi to, co powinien. Dlaczego więc wywalają mi błęda na SPOJu?

no bo popatrz na ograniczenia ;)
Te liczby są tak duże , że nie mieszczą się w std typach liczbowych ;)

klepacz napisał(a)

no bo popatrz na ograniczenia ;)
Te liczby są tak duże , że nie mieszczą się w std typach liczbowych ;)

Zmieniłem typy na zwykłe unsigned.
Problem nadal trwa:

#include <iostream>
using namespace std;
int main()
{
	register unsigned zm1 = 0;
	register unsigned zm2 = 0;
	register unsigned short stopien = 0;
    register unsigned short t = 0;
	cin >> t;
	while(t--)
	{
		cin >> zm1 >> stopien;
		stopien--;
		zm1 %= 10;
		zm2 = zm1;
		while(stopien--)
		zm1*=zm2;
		zm1%=10;
		cout << zm1 << endl;
	}
}

Próbowałem też:

#include <iostream>
using namespace std;
int main()
{
	unsigned zm1 = 0;
	unsigned zm2 = 0;
	unsigned short stopien = 0;
    unsigned short t = 0;
	cin >> t;
	while(t--)
	{
		cin >> zm1 >> stopien;
		stopien--;
		zm1 %= 10;
		zm2 = zm1;
		while(stopien--)
		zm1*=zm2;
		zm1%=10;
		cout << zm1 << endl;
	}
}

Na próżno.

Opis każdego przypadku podany jest w jednym wierszu, zawierającym dwie liczby naturalne...

Dlatego bez sensu byłoby usuwać modyfikator unsigned.

Zamiast

zm2 = zm1;

daj zm2 = 1;

http://www.algorytm.org/index.php?option=com_content&task=view&id=176&Itemid=28&PHPSESSID=79314daf0e

Co do pojemności typów - zwykły <i>int </i>to ok. od -2 do 2 miliardów więc na 1 miliard wystarczy więc czy użyjesz <i>unsigned </i>czy <i>int </i>nie ma znaczenia, tudzież użycie <i>long long</i> nie ma sensu.

Jeszcze a propos <i>register</i>, dzisiejsze kompilatory ignorują to słowo kluczowe, gdyż same dokonują optymalizacji. 
Np. kompilator Microsoftu całkowicie ignoruje <i>register</i>, nawet nie jest to żadną sugestią.

po pierwsze primo:
zamiast

while(stopien--)
                zm1*=zm2;

powinno być

while(stopien--)
                zm1=(zm1*zm2)%10;

po drugie primo
jest to bardzo powolne rozwiązanie można to policzyć nawet milion razy szybciej!

mgr.Dobrowolski napisał(a)

jest to bardzo powolne rozwiązanie można to policzyć nawet milion razy szybciej!
Naiwne potęgowanie ma złożoność O(n), szybkie potęgowanie O(log(n)), gdzie n to wykładnik, tak więc z tym milionem nie przesadzaj ;)
http://www.algorytm.org/index.php?option=com_content&task=view&id=177&Itemid=28&PHPSESSID=79314daf0e

log2(1 000 000 000) ≈ 30 razy szybciej

mgr.Dobrowolski napisał(a)

po pierwsze primo:
zamiast

while(stopien--)
                zm1*=zm2;

powinno być

while(stopien--)
                zm1=(zm1*zm2)%10;

po drugie primo
jest to bardzo powolne rozwiązanie można to policzyć nawet milion razy szybciej!

"Pierwsze Primo"

Po co "modulować" x-razy ?
Chyba lepiej raz, przed tym, a potem nie powtarzać tego działania?

"Drugie Primo"

To jak niby? Nie mogę użyć pow'a, bo mam do czynienia z liczbami int, a kiedy używam rzutowania, to buba, zła odpowiedź.

adf

Użyłem zwykłych intów. Teraz zaś przekroczono limit czasu.

Za to kiedy zmieniam zm2 = zm1 na zm2 = 1; to już całkiem mi źle potęguje.

Widzisz, przez to że używasz takich do d**y nazw zmiennych pomyliłem jedną z drugą.

        int podstawa, wykladnik, ilosc, wynik;

        cin >> ilosc;
        while(ilosc--)
        {
                cin >> podstawa >> wykladnik;
                wynik = 1;
                podstawa %= 10;
                while(wykladnik--) wynik = (wynik * podstawa) % 10;
                cout << wynik << endl;
         }

powinno być ok, nie sprawdzałem.

adf88: no sam policz, ile to jest miliard podzielić przez 30?

na moim komputerze "szybkie" daje odpowiedź natychmiast, "naiwne" po około 30 sekundach.

Glorian:
Musisz "modulować" bo przecie w prostej zmiennej nie zmieścisz 123 do potęgi 123
(prawie 260 cyfr)

Przy okazji, pisząc
zm1 *= zm2
tak na prawdę liczysz
zm1= (zm1 * zm2) % 4294967295 // 2^32-1

O pow() zapomnij

wcześniej masz "stopień--;" czyli ma być zm2=zm1;

mgr.Dobrowolski napisał(a)

adf88: no sam policz, ile to jest miliard podzielić przez 30?
zwracam honor, zmęczony mam umysł :p

masz tu szybki sposób potęgowania

pamiętaj jeszcze o jednym

(abc)%n == ((a*b) % n)%n

Da się to zrobić w złożoności O(1), wystarczy zauważyć pewną zależność, tu masz mój kod ze SPOJa:

#include <stdio.h>
#include <math.h>

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", (int)pow(a % 10, ((b - 1) % 4) + 1) % 10);
    }
    return 0;
}

mgr.Dobrowolski napisał(a)

Glorian:
Musisz "modulować" bo przecie w prostej zmiennej nie zmieścisz 123 do potęgi 123
(prawie 260 cyfr)

A, ok, zrozumiałem już.

Adf: Twój kod nie rozwiązuje problemu, poza tym 'próbował' on rozwiązać go w taki sam sposób.
Teraz mam problem z limitem czasu.

Fiu, fiu. Śliczności
Gratuluję spostrzegawczości Adamie

mgr.Dobrowolski napisał(a)

masz tu szybki sposób potęgowania

pamiętaj jeszcze o jednym

(abc)%n == ((a*b) % n)%n

Że co?
W takim razie
(234)%10 == ((2*3) % 10) % 10 ?

Adam, dzięki, to rozwiązało problem.
Gdybyś mógł mi jeszcze wytłumaczyć na czym polega twój kod ;]

Metodą doświadczalną doszedłem do wzoru:
(a ^{b) % 10 = ((a % 10)} (((b - 1) % 4) + 1)) % 10
z czego wynika że nawet przy bardzo dużych liczbach mnożeń nie będzie więcej niż 4.
I to chyba wystarczy do napisania programu, kod jest napisany w C ale możesz go łatwo przerobić na C++, dodaj odpowiednie includy, scanf'y w postaci scanf("%d", &x); zamieniasz na cin >> x; a printf("%d\n", x); to to samo co cout << x << endl;
potęgowanie a ^ b robisz za pomocą funkcji pow(a, b)

AdamW napisał(a)

Metodą doświadczalną doszedłem do wzoru:
(a ^{b) % 10 = ((a % 10)} ((b - 1) % 4) + 1) % 10
z czego wynika że nawet przy bardzo dużych liczbach mnożeń nie będzie więcej niż 4.
I to chyba wystarczy do napisania programu, kod jest napisany w C ale możesz go łatwo przerobić na C++, dodaj odpowiednie includy, scanf'y w postaci scanf("%d", &x); zamieniasz na cin >> x; a printf("%d\n", x); to to samo co cout << x << endl;
potęgowanie a ^ b robisz za pomocą funkcji pow(a, b)

No tak, rzeczywiście.
Jak również mgr. Dobrowolski gratuluję błyskotliwości ;-)

EDIT: Temat do zamknięcia.

yy.. imho, nie ma co w ogole pow'owac, mozna wszystko latwiutko stablicowac.. potrzeba gora tabliczka byte[4][10]..

0 1 2 3

0|0 0 0 0
1|1 1 1 1
2|6 2 4 8
3|1 3 9 7
4|6 4 6 4
5|5 5 5 5
6|6 6 6 6
7|1 7 9 3
8|6 8 4 2
9|1 9 1 9

poza tym:

• nie ma co wczytywac liczby A, wystarczy wczytac pominac znaki i wczytac tylko ostatnia cyfre, o to A'
• min wspolny okres = 4, czyli nie ma co wczytywac liczby B, wystarczy pominac znaki i wczytac dwie ostatnie jej cyfry, na nich %=4 i o to B'

w efekcie program mieli liczby A,B o dowolnej dlugosci, wykonujac w praktyce tylko jedno modulo i jeden odczyt z tablicy (dla formalizmu: czyli jedno przesuniecie bitowe (dlatego [4][10] a nie [10][4] !!) i dwa dodawania)

jak sie dopatrzyc regularnosci w tabeli i dorzucic pare ifow plus operacji przesuniecia bitowego moze jakas maske i moze jedno odejmowanie, to stablicowanie da sie przyciac do...

0 1

0|6 4
1|1 9

no, ale to juz wchodzimy w zakres wyscigu 'najszybsza najkrotsza binarka'..

istnieje znacznie prostsze rozwiązanie... możliwe, że trzeba je dłużej zapisywac, ale dziala zdecydowanie szybciej...
zdecydowanie szybciej..

#include <cstdio>
main()
{

int t;
scanf("%d",&t);
while (t--)
{
 int n,pot,a,j;
 scanf("%d%d",&a,&n);
 if (n==0)
    {j=0;
    }
 else if (n>0)
 { pot=a%10;
   if (pot==1)
     {
     j=1;
     }
   if (pot==2)
    {
    if(n%4==1)
              j=2;
    if(n%4==2)
              j=4;
    if(n%4==3)
              j=8;
    if(n%4==0)
              j=6;
    
    }
   if (pot==3)
    {
    if(n%4==1)
              j=3;
    if(n%4==2)
              j=9;
    if(n%4==3)
              j=7;
    if(n%4==0)
              j=1;
    
    }
   if (pot==4)
    {
    if(n%2==1)
              j=4;
    if(n%2==0)
              j=6;
    
    }
   if (pot==5)
    {
    j=5;
    }
   if (pot==6)
    {
    j=6;
    }
   if (pot==7)
    {
    if(n%4==1)
              j=7;
    if(n%4==2)
              j=9;
    if(n%4==3)
              j=3;
    if(n%4==0)
              j=1;
    
    }
   if (pot==8)
    {
    if(n%4==1)
              j=8;
    if(n%4==2)
              j=4;
    if(n%4==3)
              j=2;
    if(n%4==0)
              j=6;
    
    }
   if (pot==9)
    {
    if(n%2==1)
              j=9;
    if(n%2==0)
              j=1;
    
    }
   if (pot==0)
    {
    j=0;
    }
}
printf("%d\n",j);

}
return 0;
}

hm hm, Doro, masz rację - to sympatyczny sposób, tylko że wąż go napisał ;)
Po prostu jego wizję z tablicą rozpisałeś na ify - matematycznie używacie tego samego konceptu. No wersja z tablicą działa szybciej - z moich pobieżnych testów ok. 2x szybciej. Ale to dla małych liczb (16 bitowych) liczyłem. No i trochę ładniejsza ;)

int lookup[10][4] = {
    0,0,0,0,
    1,1,1,1,
    6,2,4,8,
    1,3,9,7,
    6,4,6,4,
    5,5,5,5,
    6,6,6,6,
    1,7,9,3,
    6,8,4,2,
    1,9,1,9
    };

int calc(int a, int n) {
    return lookup[a%10][n%4];
    }