My solution for the last digit(LASTDIG) got accepted in codechef but not getting accepted on spoj

general
,
1 
#include <iostream>
#include <cmath>
typedef long long int ll;
using namespace std;

int main() {
int t;
ll a,b,rem,res;
cin>>t;
while(t--){
cin>>a>>b;
    rem = b%a;
	res = pow(a,rem+1);
	res = res%10;
	cout<<res<<endl;
	
}
return 0;
}

link for the question: SPOJ.com - Problem LASTDIG

2

Link to the question?

3

link SPOJ.com - Problem LASTDIG

4

I bet that the constraints on both the platforms are different.
In SPOJ you can see the constraint on exponent i.e. 0 \leq b \leq 2,147,483,000 which is large enough as compare to the constraint given on Code-Chef.

To solve this problem you need to use modular exponentiation where the modulus value should be 10 as you need to find the last digit of a^b.

Source-Code for modular-exponentiation:

#include<stdio.h>
#include<stdlib.h>

#define MODULUS 10

static int compute_last_digit(int, int);

int main(void) {
	int test;
	scanf("%d", &test);
	while(test--) {
		int a, b;
		scanf("%d%d", &a, &b);
		printf("%d\n", compute_last_digit(a, b));
	}
	return EXIT_SUCCESS;
}

static int compute_last_digit(int base, int exponent) {
	int result;
	if(!base) {
		result = 0;
	} else if(!exponent) {
		result = 1;
	} else {
		result = 1;
		while(exponent) {
			if(exponent & 1) {
				result = (result * (base)) % MODULUS;
			}
			base = (base * base) % MODULUS;
			exponent >>= 1;
		}
	}
	return result;
}

EDIT: I haven’t worked with the boost/multiprecision in C++, so you can try if you want and if the ONLINE JUDGE also supports the library, then your program will be accepted on both platforms as Code-Chef platform is based on SPOJ. But I don’t recommend it, as there is a simple iterative approach to solve the problem as coded above in C.

Accepted solution on Code-Chef, but it will not be accepted in SPOJ due to size error, in SPOJ there is size limit on the source-code i.e. 700 bytes means your source-code should only have 700 characters. Follow the above written-source code for acceptance in SPOJ.

Thanks for reading.
Peace :v:

4 Likes
5

can’t I use boost/multiprecision in c++

6

thanks for the help. I really appreciate it

1 Like
7

No problem :slight_smile:

8

The best way is to note that each last digit has a cycle associated with it.

Eg: 3 – 9 – 7 – 1 – 3 (3 * 3 is 9 and so on)

And the interesting part is none of them exceed 4.
Just find the number of times you need to multiply the last digit to get the same last digit. Then use b %= cnt, and boom. Just multiply the number b more time to get the answer. But you should actually implement the way @striker22 showed it to you. It will help you later when required.

One similar problem associated with it is:

GCDMOD.

Hope you have fun solving it. :slight_smile:

3 Likes