SPOJ - czy umiesz potęgować

0

Witam,

kolejny raz wyrzuca mi błąd na SPOJu przy banalnym zadaniu -> https://pl.spoj.com/problems/PA05_POT/
Jest ktoś w stanie mnie nakierować dlaczego? Według mnie jest wszystko ok, kod:

using System;
namespace ConsoleApp53
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = Convert.ToInt32(Console.ReadLine());

            while (count > 0)
            {
                string[] ab = Console.ReadLine().Split(' ');
                double a = Convert.ToDouble(ab[0]);
                double b = Convert.ToDouble(ab[1]);

                double res = Math.Pow(a, b);

                if (res >= 10) res -= (Math.Floor(res / 10) * 10);

                Console.WriteLine(res);
                count--;
            }
            Console.ReadKey();
        }
    }
}
1

E panie tak to raczej tego się nie robi. Ostatnia cyfra powtarza się w zależności od liczby podnoszonej do potęgi. Więc tak na prawdę nie potęgujesz tylko sprawdzasz co ma być podniesione do jakie potęgi i sprawdzasz okres powtarzalności ostatniej cyfry.

np

2^1 =2
2^2 = 4
2^3 = 8
2^4= 16
2^5=32 - tu się powtarza dwójka
potem 4-ka (64) itd

Więc jesteś wstanie sprawdzić jaka będzie ostatnia cyfra przy np 2^2455 bez obliczania

0

Niby wszystko ok, ale jak dostaniesz na przykład 9^3598203 to jak zachowa się Twój program? Nie musisz liczyć tego wyrażenia (powodzenia!) żeby znać jego ostatnią cyfrę.

1

Poprawiona wersja według https://brilliant.org/wiki/finding-the-last-digit-of-a-power/

class Program
{
    static void Main(string[] args)
    {
        int count = Convert.ToInt32(Console.ReadLine());

        while (count-- > 0)
        {
             string[] ab = Console.ReadLine().Split(' ');
            long a = Convert.ToInt64(ab[0]);
            long b = (Convert.ToInt64(ab[1]) - 1) % 4;

            long result = a % 10;
            while (b-- > 0)
            {
                result = (result * a) % 10;
            }

            Console.WriteLine(result);                
        }

    }
}
1

Optymalnie byłoby zrobić tak jak podlinkował @szydlak : https://zapytaj.onet.pl/Categ[...]_bardzo_duzym_wykladniku.html , ale przejdzie też rozwiązanie z potęgowaniem modularnym, Użyj tej funkcji: https://docs.microsoft.com/pl[...].modpow?view=netframework-4.8 ; (ModPow(a, b, 10)). Złożoność O(logn), czyli tutaj max trzydzieści operacji na jedno działanie.

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