in Competitive programming

SPOJ LASTDIG solution

Solution for problem http://www.spoj.com/problems/LASTDIG/ from SPOJ website.

Sometimes I stuck solving some problems from there (usually because my code either add unneeded new line or doesn’t add needed new line and I am finding what is wrong by trial and error), so here is working solution for LASTDIG that can save you time if you encounter some strange Wrong Answer or NZEC errors.

The idea is that the last digit of power of number has some period. For example, for number 2 (and same applies to number 12, 22, 32 and so on, because last digit is always result of multiplication of last digits), we have:

Number | Last digit
-------------------
2      | 2 
4      | 4
8      | 8
16     | 6
32     | 2
64     | 4
128    | 8
256    | 6
512    | 2
...

C++ Solution:

(before sending to SPOJ, remove whitespaces or otherwise you will hit 700B size limit for problem)

#include <bits/stdc++.h>

using namespace std;

int solve(int a, long long b)
{
    static const int periods[10][5] = {
        {0,0,0,0,0},
        {1,0,0,0,0},
        {2,4,8,6,0},
        {3,9,7,1,0},
        {4,6,0,0,0},
        {5,0,0,0,0},
        {6,0,0,0,0},
        {7,9,3,1,0},
        {8,4,2,6,0},
        {9,1,0,0,0}
    };

    if (a != 0 && b == 0) return 1;
    a = a % 10;

    const int* period = periods[a];
    int periodLength = 0;
    for (;period[periodLength];++periodLength);

    if (periodLength == 0) return 0;
    int modulo = (b - 1) % periodLength;
    return period[modulo];
}

int main()
{
    int T, a;
    long long b;
    scanf("%d\n", &T);

    for (int i = 0; i < T; ++i) {
        scanf("%d %lld", &a, &b);
        cout << solve(a,b) << endl;
    }
    return 0;
}

 

Python 3.5 solution:

import sys

N = int(sys.stdin.readline())
for i in range(0, N):
    a, b = sys.stdin.readline().split()
    a, b = int(a), int(b)
    res = pow(a, b, 10)
    sys.stdout.write(str(res) + "\n")

 

Write a Comment

Comment